用两种方式实现表达式自动计算

用两种方式实现表达式自动计算-1-数据结构（双语）——项目文档报告用两种方式实现表达式自动计算专业：计算机科学与技术应用班级：指导教师：吴亚峰姓名：学号：用两种方式实现表达式自动计算-2-目录一、设计思想……………………………………………………….01二、算法流程图…………………………………………………….01三、源代码………………………………………………………….03四、运行结果……………………………………………………….15五、遇到的问题及解决…………………………………………….16六、心得体会……………………………………………………….17用两种方式实现表达式自动计算-3-一、设计思想A:中缀表达式转后缀表达式的设计思想：我们借助计算机计算一个算数表达式的值，而在计算机中，算术表达式是由常量，变量，运算符和括号组成。由于运算符的优先级不同又要考虑括号。所以表达式不可能严格的从左到右进行，因此我们借助栈和数组来实现表达式的求值。栈分别用来存储操作数和运算符。在计算表达式的值之前，首先要把有括号的表达式转换成与其等值的无括号的表达式，也就是通常说的中缀表达式转后缀表达式。在这个过程中，要设计两个栈，一个浮点型的存储操作数，用以对无符号的表达式进行求值。另一个字符型的用来存储运算符，用以将算术表达式变成无括号的表达式；我们要假设运算符的优先级：(),*/,+-。首先将一标识号‘#’入栈，作为栈底元素；接着从左到右对算术表达式进行扫描。每次读一个字符，若遇到左括号‘（’，则进栈；若遇到的是操作数，则立即输出；若又遇到运算符，如果它的优先级比栈顶元素的优先级数高的话，则直接进栈，否则输出栈顶元素，直到新的栈顶元素的优先级数比它低的，然后将它压栈；若遇到是右括号‘）’，则将栈顶的运算符输出，直到栈顶的元素为‘（’，然后，左右括号互相底消；如果我们设计扫描到‘#’的时候表示表达式已经扫描完毕，表达式已经全部输入，将栈中的运算符全部输出，删除栈底的标识号。以上完成了中缀表达式转后缀表达式，输出无括号的表达式，若遇数值，操作数进栈；若遇运算符，让操作数栈的栈顶和次栈顶依次出栈并与此运算符进行运算，运算结果入操作数栈；重复以上的步骤，直到遇到‘#’，则此时栈中的结果便是所求的后缀表达式的值，接着输出结果。以上就是设计这个算法的主要的思想。设计思想的流程图详见图A；B:直接计算表达式的值。所谓的扫一遍就是当扫完一个表达式结果也就计算出来了，是在上面扫两遍的思想进行修改的得来，首先，我们要建立两个栈，一个为字符型的用来存放运算符，另一个浮点型的用来存放操作数。我们开始对表达式进行扫描，首先我们要假设运算符的优先级：(),*/,+-。如果扫描到的是数字符号，把它们转换成浮点型数据，存入操作数栈中。如果扫描到的是运算符号，第一个运算符进栈，遇到‘（’存入运算符栈中，我们按照第一种算法的方法将表达式依次扫描。只不过不同的是，当每取得的一个运算符的时候，都要与栈顶的运算符进行比较，如果它的优先级小于栈顶运算符优先级时，取出栈顶运算符并从操作数栈中取栈顶两个数进行运算，得到的结果则要存回操作数栈，就这样边扫描边比较，再进行计算。遇到“）”对运算符的处理相同。扫描结束后，把运算符栈的元素和操作数栈里的数进行运算。每次的运算结果再放入操作数栈，一直到计算到运算符栈空。最后操作数栈的栈顶留下的操作数即表达式的计算结果。以上就是设计这个扫一遍算法的主要的思想。设计思想的流程图详见图B；二、算法流程图用两种方式实现表达式自动计算-4-A:以下是中缀转后缀算法的流程图图2是中缀转后缀算法的流程图用两种方式实现表达式自动计算-5-B：以下是扫一遍代码运算的流程图：图B是直接计算的流程图三、源代码A：下面给出的是用中缀表达式转后缀表达式算法实现的程序的源代码：#includestdio.h/*I/O函数*/#includemalloc.h#includestdlib.h#defineMAXLEN100/*对栈的最大存贮值进行定义*/用两种方式实现表达式自动计算-6-/*自定义两个栈*/typedefstructstackData{floatdata[MAXLEN];inttop;/*指针*/}stackData;/*定义存储操作数的栈*/typedefstructstackChar{chardata[MAXLEN];inttop;/*指针*/}stackChar;/*用于定义存储操作符号的栈*//*对相应的函数和常量变量，指针进行声明*/intjudgeFirst(charc);/*声明判定操作符优先级的函数*/intPushNum(stackData*p,floatvalue);/*入栈*/intPushChar(stackChar*p,charvalue);intPopNum(stackData*p,float*value);/*出栈*/intPopChar(stackChar*p,char*value);floatVisitNum(stackData*p);charvisitChar(stackChar*p);floatCompute(floata,charch,floatb);/*操作函数，执行具体运算*/intCheck(char*);stackData*Data;/*定义操作数栈，由指针data指出*/stackChar*Operation;stackData*InitNum();stackChar*InitChar();inti,j=0;floatbl,blo;/*对变量进行声明*/floatresoult,opA,opB;charoperand[2],opChar;/*定义字符型数组和字符变量*/charrecv[MAXLEN];floatsuffix[MAXLEN];char*ptRecv=NULL;/*定义字符型指针*/intmain()/*主函数*/{printf(pleaseentertneformula:);while((scanf(%s,recv))!=EOF)/*判断循环的条件当输入EOF的时候停止*/{Operation=InitChar();Data=InitNum();PushChar(Operation,'#');用两种方式实现表达式自动计算-7-recv[strLen(recv)]='#';/*将字符#赋予数组最后*/ptRecv=recv;for(i=0;istrLen(ptRecv);i++)/*扫描表达式，判断循环的条件*/{if(recv[i]='0'&&recv[i]='9'||recv[i]=='.')/*判断数值*/{doubleweight=0.1;intflag=0;/*定义变量flag，用来标志小数点*/floatblo=0;/*定义浮点型变量*/blo=recv[i]-'0';while(recv[i+1]='0'&&recv[i+1]='9'||recv[i+1]=='.')/*判定数值*/{if(recv[i+1]=='.')/*读到小数点*/flag=1;else{if(flag==0)blo=blo*10+recv[i+1]-'0';/*将整数部分字符串转化为实数*/else{blo=blo+(recv[i+1]-'0')*weight;/*将表示小数部分的字符也转化过来*/weight*=0.1;/*weight为小数位权*/}}i++;}suffix[j]=blo;j++;/*数值进入数组*/}else{if(recv[i]=='#')/*遇见字符#*/{while(visitChar(Operation)!='#')/*对操作符栈进行遍历*/{PopChar(Operation,&opChar);suffix[j]=opChar;j++;/*字符出栈进入数组*/}}else{if(judgeFirst(recv[i])judgeFirst(visitChar(Operation))||visitChar(Operation)=='(')/*判断操作符的优先级高低*/{用两种方式实现表达式自动计算-8-PushChar(Operation,recv[i]);/*字符入栈*/}else{if(recv[i]==')')/*遇见字符）*/{while(visitChar(Operation)!='(')/*输出（之前的所有操作符*/{PopChar(Operation,&opChar);suffix[j]=opChar;j++;/*操作符进入数组*/}PopChar(Operation,&opChar);}else{while(judgeFirst(recv[i])=judgeFirst(visitChar(Operation)))/*进栈的运算符优先级低时，先出栈后进栈*/{PopChar(Operation,&opChar);suffix[j]=opChar;/*出栈的进入数组*/j++;}PushChar(Operation,recv[i]);/*运算符进栈*/}}}}}printf(thesuffixis:);/*输出后缀表达式*/for(j=0;suffix[j]!='\0';j++){if((char)suffix[j]=='+'||(char)suffix[j]=='-'||(char)suffix[j]=='*'||(char)suffix[j]=='/')/*强制类型转换*/{printf(%6c,(char)suffix[j]);/*输出一个运算符*/PopNum(Data,&opA);PopNum(Data,&opB);resoult=Compute(opB,(char)suffix[j],opA);/*调用函数进行运算*/PushNum(Data,resoult);/*运算结果入栈*/}else{用两种方式实现表达式自动计算-9-PushNum(Data,suffix[j]);printf(%10f,suffix[j])/*输出后缀表达式*/;}}printf(\ntheResultis:%.2f\n\n,resoult);/*输出运算结果*/}return0;}stackData*InitNum()/*初始化数值栈*/{stackData*p=(stackData*)malloc(sizeof(stackData));/*取一段内存赋予数值栈*/p-top=-1;/*定义栈底*/returnp;/*返回数值栈*/}stackChar*InitChar()/*初始化操作符栈*/{stackChar*p=(stackChar*)malloc(sizeof(stackChar));/*取一段内存赋予操作符栈*/p-top=-1;returnp;}intPushNum(stackData*p,floatvalue)/*定义入栈函数*/{if(p-topMAXLEN-1){p-top+=1;/*指针*/p-data[p-top]=value;/*入栈的数值为栈顶元素*/return1;}else{return0;}}intPushChar(stackChar*p,charvalue)/*定义操作符入栈函数*/{if(p-topMAXLEN-1)/*栈不能满*/{p-top+=1;/*指针*/p-data[p-top]=value;/*入栈字符为栈顶元素*/return1;}用两种方式实现表达式自动计算-10-else{return0;/*栈溢出返回0*/}}intPopNum(stackData*p,float*value)/*定义数值出栈函数*/{if(p-top=0)/*判定栈不为空*/{*value=p-data[p-top];p-top-=1;/*指针*/}return1;}intPopChar(stackChar*p,char*value)/*定义操作符出栈函数*/{if(p-top=0)/*判