c++两种方法实现表达式的计算

数据结构（双语）——项目文档报告用两种方式实现表达式自动计算专业：网络工程班级：网络1班指导教师：吴亚峰姓名：王嘉宇学号：201214620111目录一、设计思想……………………………………………………….01二、算法流程图…………………………………………………….01三、源代码………………………………………………………….04四、运行结果……………………………………………………….12五、遇到的问题及解决…………………………………………….13六、心得体会……………………………………………………….1401一、设计思想（1）先将中缀表达式转化为后缀表达式，再通过计算后缀表达式求表达式的值。第一遍扫描中缀表达式，需要一个运算符栈和一个数组。运算符栈用来存放运算符，数组用来存放转换成的后缀表达式。首先将中缀表达式挨个扫描。如果是数字，则直接放在后缀表达式数组中，依次存放。如果扫描到的是运算符，则按照以下规则存放：栈空时，任何运算符可直接入栈。栈不空是，如果栈中运算符的优先级高于或等于将要放入栈中的运算符的优先级，则将栈中运算符出栈，放入后缀表达式数组中，直到栈中运算符优先级低于将要放入栈中的运算符的优先级，此时将此运算符放入运算符栈中。如果遇到左括号，则直接将左括号入栈，左括号入栈后优先级最低，其他运算符可直接放入。如果遇到右括号，则将运算符栈中的运算符依次取出放到后缀表达式数组中，直到遇到左括号为止，此时将左括号从栈顶删除。按此方法，直到后缀表达式转换成功。第二遍扫描后缀表达式，此时需要一个数栈。扫描时如果遇到数字，则直接放到数栈中。如果遇到运算符，则将数栈中两个数取出，先取出的放在运算符后面，后取出的放在运算符前面，进行运算符运算。将运算的结果放入栈中。之后接着扫描后缀表达式。另外因为运算数的位数不一定而且还有小数点，所以在扫到一个数时要判断这个数的位数，将这个完整的运算数字符串整个取出，这需要用到一个辅助索引。当栈中只有一个数字时，这个数字就是我们要求的表达式的值。（2）直接计算表达式的值。这种方法需要两个栈，一个运算符栈，一个数栈。只需扫描一遍中缀表达式，边运算边入栈。当扫描到的为数字是，将其放入数栈中，然后扫描下一个字符。如果扫描到的是运算符，栈空时，任何运算符可直接入栈。栈不空是，如果栈中运算符的优先级高于或等于将要放入栈中的运算符的优先级，则将栈中运算符出栈，并从数栈中取出两个数，先取出的放在后面，后取出的放在前面，进行运算符运算，得出结果后，将其放入数栈中。如果栈顶运算符优先级依然高于或等于将要入栈的运算符优先级，仍然进行以上操作，直到栈顶运算符低于将要放入栈中的的运算符的优先级，此时将该运算符入栈。如果扫描到的是左括号，则直接将其入栈。如果扫描到的是右括号，则将栈顶运算符取出，进行以上运算，直到栈顶为左括号，此时将栈顶左括号删除即可，然后将运算结果放入数栈中。当中缀表达式扫描完，并且运算符栈中全部出栈，数栈中只剩一个数字时，即为运算结果。另外因为运算数的位数不一定而且还有小数点，所以在扫到一个数时要判断这个数的位数，将这个完整的运算数字符串整个取出，这需要用到一个辅助索引。二、算法流程图图1是从中缀表达式转为后缀表达式并对后缀表达式进行计算的算法流程图，图中所有图形都是长方形，按箭头顺序依次执行。其中如果箭头向下方向有分叉，则箭头左侧长方形代表“是”，右侧代表“否”。图2是中缀表达式直接计算的算法流程图。按箭头方向执行。图中如果遇到选择类型的语句，则在箭头有分叉的下一行语句中先声明了选项，然后与后面语句逗号隔开。具体流程图如下：02图1中缀转后缀再计算算法流程图中缀表达式扫描完毕运算符栈中元素全部输出放入后缀表达式数组exp[len]中从后缀表达式中取元素ch=exp[t],t++是否为数存入数栈中从数栈中取出两个数进行运算符运算，得出结果放入数栈输出栈里最终栈顶元素即为所求结束ch是否为（运算符栈为空或者栈运算符优先级低于ch优先级将ch放入运算符栈中将栈顶运算符出栈放入后缀表达式中，直到栈顶元素优先级低于ch优先级，此时将ch入栈将ch入栈将操作符栈中元素取出放入后缀表达式中，直到栈顶元素为（用户输入表达式将表达式赋给str[len]构造运算符栈和数栈扫描中缀表达式ch=str[i],i++ch是否为数将ch直接放入后缀表达式数组中ch是否为+-*/%03图2中缀表达式直接计算算法流程图栈顶元素是否为（是，pop出左括号操作符栈是否为空不是，取出数栈中两个数，计算后存入数栈为空，取出数栈中的数作为返回值不为空，取出数栈中两个数，计算后存入数栈，作为返回值得到存放中缀表达式的数组运算符，与栈顶比较优先级操作符，判断是运算符还是括号数字或小数点，截取子串并将其转换成double型存入数栈中判断字符类型依次取出数组中的每个字符右括号，取出栈顶元素左括号，直接入操作符栈判断是哪个括号入操作符栈不高于栈顶，取出数栈中两个数，计算后存入数栈结束04三、源代码下面给出的是用中缀表达式转换为后缀表达式再进行计算的算法实现的程序的源代码：#includestdio.h//导入要用的包#includestdlib.h#includemath.h#definelen1000structopnode{chardata[len];inttop;}op;//定义字符栈structodnode{inttop;floatdata[len];}od;//定义数栈voidtrans(charstr[],charexp[],structopnodeop)//中缀变后缀的方法{charch;inti=0,t=0;op.top=-1;//初始字符栈顶为空od.top=-1;//初始数栈顶为空ch=str[i];i++;//定义存放字符串的数组while(ch!='\0')//数组中字符串不为空{switch(ch){case'+'://判断是否是'+'、'-'case'-':while(op.top!=-1&&op.data[op.top]!='(')//栈不为空且栈顶符号不为'('{exp[t++]=op.data[op.top--];//存放后缀表达式的数组添加元素}op.top++;op.data[op.top]=ch;//入栈break;case'*'://判断是否是'*'、'/'、'%'case'/':case'%':while(op.data[op.top]=='*'||op.data[op.top]=='/'||op.data[op.top]=='%'){exp[t++]=op.data[op.top--];05}//栈顶元素为'*'或'/'，存放后缀表达式的数组添加元素op.top++;op.data[op.top]=ch;//入栈break;case'(':op.top++;op.data[op.top]=ch;break;//扫描若是'(',入栈case')':while(op.data[op.top]!='(')//不是左括号出栈{exp[t++]=op.data[op.top--];}//栈顶元素不为'('，出栈op.top--;//'('出栈break;case'=':break;default:while(ch='0'&&ch='9'||ch=='.'){exp[t++]=ch;ch=str[i++];}//扫描是否是数字或小数点，存入数组i--;exp[t]='|';t++;//分隔后缀中的数值元素break;}ch=str[i];i++;}while(op.top!=-1)//栈顶不为空{exp[t++]=op.data[op.top];op.top--;}//将栈顶元素赋给后缀表达式直到栈为空exp[t]='\0';}floatcount(charexp[])//后缀计算的方法{floatd=0;charch,tran[len];intt=0,i=0;ch=exp[t];t++;while(ch!='\0'){switch(ch){case'+':od.data[od.top-1]=od.data[od.top-1]+od.data[od.top];od.top--;//数栈中取值相加break;06case'-':od.data[od.top-1]=od.data[od.top-1]-od.data[od.top];od.top--;//数栈中取值相减break;case'*':od.data[od.top-1]=od.data[od.top-1]*od.data[od.top];od.top--;//数栈中取值相乘break;case'/':if(od.data[od.top]!=0){od.data[od.top-1]=od.data[od.top-1]/od.data[od.top];od.top--;//数栈中取值相除}else{printf(\n0不能做被除数\n);//若除数为0则输出此语句}break;case'%':if(od.data[od.top-1]!=0){od.data[od.top-1]=fmod(od.data[od.top-1],od.data[od.top]);od.top--;//数栈中取值取余}else{printf(0不能被任何值取余);}//若除数为0输出此语句break;default:while(ch='0'&&ch='9'||ch=='.')//扫描是否是数字或小数点{tran[i]=ch;//把元素存入字符串i++;ch=exp[t];t++;}tran[i]='\0';//结束表示数字的字符串i=0;d=atof(tran);//字符串转化成数od.top++;od.data[od.top]=d;}ch=exp[t];t++;}returnod.data[od.top];//返回计算结果}main(){07charstr[len],exp[len];structopnodeop;printf(输入一个计算表达式：\n);gets(str);trans(str,exp,op);printf(后缀表达式：%s\n,exp);printf(表达式结果：%f\n,count(exp));scanf(%d\n);return0;}下面给出的是用中缀表达式直接进行计算的算法实现的程序的源代码：#includestdio.h#includestring.h#includestdlib.h/*包含库函数*/#defineMAX100/*定义栈的最大长度*/structopnode/*声明op栈*/{charstr[MAX];inttop_op;};structodnode/*声明od栈*/{doublenum[MAX];inttop_od;};voidpush_op(structopnode*op,charc)/*定义op栈的进栈函数*/{if(op-top_op=MAX-1)/*如果栈满，不进行操作*/{}else/*否则，进行进栈操作*/{op-top_op++;op-str[op-top_op]=c;}}voidpop_op(structopnode*op)/*定义op栈的出栈函数*/{if(op-top_op=-1)/*如果栈为空，不进行操作*/{}else/*否则，进行出栈操作*/{08op-top_op--;}}chartop_op(structopnode*op)/*定义op栈的看栈顶的函数*/{return(op-str[op-top_op]);}/***************/voidpush_od(structodnode*od,doubled)/*定义od栈的进栈函数*/{if(od-top_od=MAX-1)/*如果栈为满，不进行操作*/{}else/*否则，进行进栈操作*/{od-top_od++;od-num[od-top_od]=d;}}voidpop_od(stru