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

1、数据结构（双语）项目文档报告用两种方式实现表达式自动计算专 业： 网络工程 班 级： 网络1班 指导教师： 吴亚峰 姓 名： 王嘉宇 学 号： 1 目 录一、设计思想.01二、算法流程图.01三、源代码.04四、运行结果.12五、遇到的问题及解决.13六、心得体会.14一、设计思想（1）先将中缀表达式转化为后缀表达式，再通过计算后缀表达式求表达式的值。第一遍扫描中缀表达式，需要一个运算符栈和一个数组。运算符栈用来存放运算符，数组用来存放转换成的后缀表达式。首先将中缀表达式挨个扫描。如果是数字，则直接放在后缀表达式数组中，依次存放。如果扫描到的是运算符，则按照以下规则存放：栈空时，任何运算符可直

2、接入栈。栈不空是，如果栈中运算符的优先级高于或等于将要放入栈中的运算符的优先级，则将栈中运算符出栈，放入后缀表达式数组中，直到栈中运算符优先级低于将要放入栈中的运算符的优先级，此时将此运算符放入运算符栈中。如果遇到左括号，则直接将左括号入栈，左括号入栈后优先级最低，其他运算符可直接放入。如果遇到右括号，则将运算符栈中的运算符依次取出放到后缀表达式数组中，直到遇到左括号为止，此时将左括号从栈顶删除。按此方法，直到后缀表达式转换成功。第二遍扫描后缀表达式，此时需要一个数栈。扫描时如果遇到数字，则直接放到数栈中。如果遇到运算符，则将数栈中两个数取出，先取出的放在运算符后面，后取出的放在运算符前面，进

3、行运算符运算。将运算的结果放入栈中。之后接着扫描后缀表达式。另外因为运算数的位数不一定而且还有小数点，所以在扫到一个数时要判断这个数的位数，将这个完整的运算数字符串整个取出，这需要用到一个辅助索引。当栈中只有一个数字时，这个数字就是我们要求的表达式的值。（2）直接计算表达式的值。这种方法需要两个栈，一个运算符栈，一个数栈。只需扫描一遍中缀表达式，边运算边入栈。当扫描到的为数字是，将其放入数栈中，然后扫描下一个字符。如果扫描到的是运算符，栈空时，任何运算符可直接入栈。栈不空是，如果栈中运算符的优先级高于或等于将要放入栈中的运算符的优先级，则将栈中运算符出栈，并从数栈中取出两个数，先取出的放在后面

4、，后取出的放在前面，进行运算符运算，得出结果后，将其放入数栈中。如果栈顶运算符优先级依然高于或等于将要入栈的运算符优先级，仍然进行以上操作，直到栈顶运算符低于将要放入栈中的的运算符的优先级，此时将该运算符入栈。如果扫描到的是左括号，则直接将其入栈。如果扫描到的是右括号，则将栈顶运算符取出，进行以上运算，直到栈顶为左括号，此时将栈顶左括号删除即可，然后将运算结果放入数栈中。当中缀表达式扫描完，并且运算符栈中全部出栈，数栈中只剩一个数字时，即为运算结果。另外因为运算数的位数不一定而且还有小数点，所以在扫到一个数时要判断这个数的位数，将这个完整的运算数字符串整个取出，这需要用到一个辅助索引。二、算法

5、流程图图1是从中缀表达式转为后缀表达式并对后缀表达式进行计算的算法流程图，图中所有图形都是长方形，按箭头顺序依次执行。其中如果箭头向下方向有分叉，则箭头左侧长方形代表“是”，右侧代表“否”。图2是中缀表达式直接计算的算法流程图。按箭头方向执行。图中如果遇到选择类型的语句，则在箭头有分叉的下一行语句中先声明了选项，然后与后面语句逗号隔开。具体流程图如下：中缀表达式扫描完毕运算符栈中元素全部输出放入后缀表达式数组explen中从后缀表达式中取元素ch=expt,t+是否为数存入数栈中从数栈中取出两个数进行运算符运算，得出结果放入数栈输出栈里最终栈顶元素即为所求结束ch是否为（运算符栈为空或者栈运算

6、符优先级低于ch优先级将ch放入运算符栈中将栈顶运算符出栈放入后缀表达式中，直到栈顶元素优先级低于ch优先级，此时将ch入栈将ch入栈将操作符栈中元素取出放入后缀表达式中，直到栈顶元素为（用户输入表达式将表达式赋给strlen构造运算符栈和数栈扫描中缀表达式ch=stri,i+ch是否为数将ch直接放入后缀表达式数组中ch是否为+-*/% 图1 中缀转后缀再计算算法流程图栈顶元素是否为（是，pop出左括号操作符栈是否为空不是，取出数栈中两个数，计算后存入数栈为空，取出数栈中的数作为返回值不为空，取出数栈中两个数，计算后存入数栈，作为返回值得到存放中缀表达式的数组运算符，与栈顶比较优先级操作符，

7、判断是运算符还是括号数字或小数点，截取子串并将其转换成double型存入数栈中判断字符类型依次取出数组中的每个字符右括号，取出栈顶元素左括号，直接入操作符栈判断是哪个括号入操作符栈不高于栈顶，取出数栈中两个数，计算后存入数栈结束图2 中缀表达式直接计算算法流程图三、源代码下面给出的是用中缀表达式转换为后缀表达式再进行计算的算法实现的程序的源代码：#include/导入要用的包#include#include#define len 1000 struct opnode char datalen; int top; op;/定义字符栈 struct odnode int top;float dat

8、alen; od;/定义数栈void trans(char str,char exp,struct opnode op)/中缀变后缀的方法 char ch; int i=0,t=0; op.top=-1;/初始字符栈顶为空 od.top=-1; /初始数栈顶为空 ch=stri;i+; /定义存放字符串的数组 while(ch!=0)/数组中字符串不为空 switch(ch) case+: /判断是否是+、- case-: while(op.top!=-1&op.dataop.top!=()/栈不为空且栈顶符号不为( expt+=op.dataop.top-;/存放后缀表达式的数组添加元素 o

9、p.top+; op.dataop.top=ch;/入栈 break; case*: /判断是否是*、/、% case/: case%: while(op.dataop.top=*|op.dataop.top=/|op.dataop.top=%) expt+=op.dataop.top-; /栈顶元素为*或/，存放后缀表达式的数组添加元素 op.top+; op.dataop.top=ch;/入栈 break; case(: op.top+;op.dataop.top=ch;break;/扫描若是(,入栈 case): while(op.dataop.top!=()/不是左括号出栈 expt+

10、=op.dataop.top-; /栈顶元素不为(，出栈 op.top-;/(出栈 break; case=:break; default: while(ch=0&ch=0&ch=9|ch=.)/扫描是否是数字或小数点 trani=ch;/把元素存入字符串i+;ch=expt;t+;trani=0;/结束表示数字的字符串i=0;d=atof(tran);/字符串转化成数od.top+;od.dataod.top=d; ch=expt;t+;return od.dataod.top;/返回计算结果main() char strlen,explen;struct opnode op;printf(

11、输入一个计算表达式：n);gets(str);trans(str,exp,op); printf(后缀表达式：%sn,exp);printf(表达式结果： %fn,count(exp);scanf(%dn);return 0;下面给出的是用中缀表达式直接进行计算的算法实现的程序的源代码：#include #include #include /*包含库函数*/#define MAX 100/*定义栈的最大长度*/struct opnode/*声明op栈*/char strMAX;int top_op;struct odnode/*声明od栈*/double numMAX;int top_od;v

12、oid push_op(struct opnode *op,char c)/*定义op栈的进栈函数*/if(op-top_op=MAX-1)/*如果栈满，不进行操作*/else/*否则，进行进栈操作*/op-top_op+;op-strop-top_op=c;void pop_op(struct opnode *op)/*定义op栈的出栈函数*/if(op-top_optop_op-;char top_op(struct opnode *op)/*定义op栈的看栈顶的函数*/return(op-strop-top_op); /*/void push_od(struct odnode *od,d

13、ouble d)/*定义od栈的进栈函数*/if(od-top_od=MAX-1)/*如果栈为满，不进行操作*/else/*否则，进行进栈操作*/od-top_od+;od-numod-top_od=d;void pop_od(struct odnode *od)/*定义od栈的出栈函数*/if(od-top_odtop_od-;double top_od(struct odnode *od)/*定义od栈看栈顶的函数*/return(od-numod-top_od); /*判断是否为运算符*/int is_op(char op)/*op为运算符*/switch(op)/*用switch语句判

14、断*/case (:return 1;break;case ):return 1;break;case +:return 1;break;case -:return 1;break;case *:return 1;break;case /:return 1;break;case %:return 1;break;/*如果是运算符，返回1*/default:return 0;break;/*否则，返回0*/*判断运算符优先级*/int level(char op)/*op为运算符*/switch(op)/*用switch语句判断，返回值为运算符的栈内优先级*/case #:return 0;br

15、eak;/*#作为栈底元素*/case ):return 0;break;/*如果是#或)，返回0*/case (:return 1;break;/*如果是（，返回0*/case +:return 2;break;case -:return 2;break;/*如果是+或-，返回2*/case *:return 3;break;case /:return 3;break;case %:return 3;break;/*如果是*,/或%，返回3*/default:return 0;break;/*计算*/double re(double a,double b,char op)/*计算两个浮点数的

16、运算结果*/switch(op)/*用switch语句判断，op为运算符*/case +:return a+b;/*返回a和b的和*/break;case -:return a-b;/*返回a和b的差*/break;case *:return a*b;/*返回a和b的积*/break;case /:if(b=0.0)return 0;/*返回a和b的商*/else return a/b; /*如果b=0，返回0，计算结果出错，但程序不会强行终止*/break;case %:return (int)a%(int)b;/*返回a取余b的结果*/break;default:return 0;brea

17、k;/*否则，返回0*/ /*主函数*/void main() int i,inpos;/*inpos是inorder100的扫描索引*/ char inorderMAX;/*用于存储表达式*/ char c,*p=NULL;/*atof()函数所用的指针*/ double a,b,result; char temp_op;struct opnode oplist;/*定义op栈*/struct odnode odlist;/*定义od栈*/struct opnode *op;/*定义op栈的指针*/struct odnode *od;/*定义od栈的指针*/op=&oplist;od=&od

18、list;od-top_od=-1;/*初始化od栈*/op-top_op=-1;/*初始化op栈*/c=#;push_op(op,c);/*向op栈栈底放入#，用于进栈时判断优先级*/printf(输入一个中缀表达式(直接计算):n);/*提示信息*/gets(inorder);/*接收表达式*/*扫描表达式*/i=0;/*i作为扫描inorder100的辅助索引*/inpos=0;/*初始化扫描索引*/c=inorderinpos;while(c!=0)/*用while循环扫描数组inorder100*/c=inorderinpos;i=inpos;if(c=0&c=0&inorderil

19、evel(top_op(op)|c=()/*如果操作符优先级大，压入op栈中*/push_op(op,c);else if(c=)/*如果操作符是)*/temp_op=top_op(op);while(temp_op!=()/*从op栈中出栈，直到栈顶为(*/temp_op=top_op(op);pop_op(op);/*从op栈中取出一个操作符*/b=top_od(od);pop_od(od);a=top_od(od);pop_od(od);/*从od栈中依次取出两个数字*/result=re(a,b,temp_op);/*计算两个数字的运算结果*/push_od(od,result);/*

20、将结果压入od栈中*/temp_op=top_op(op);pop_op(op);/*将(出栈*/else if(level(c)=level(top_op(op)/*如果操作符优先级低*/dotemp_op=top_op(op);pop_op(op);/*从op栈中取出一个操作符*/b=top_od(od);pop_od(od);a=top_od(od);pop_od(od);/*从od栈中依次取出两个数字*/result=re(a,b,temp_op);/*计算两个数字的运算结果*/push_od(od,result);/*将结果压入od栈中*/while(level(c)top_op0)

21、/*如果op栈中还有操作符*/temp_op=top_op(op);pop_op(op);/*从op栈中取出一个操作符*/b=top_od(od);pop_od(od);a=top_od(od);pop_od(od);/*从od栈中依次取出两个数字*/result=re(a,b,temp_op);/*计算两个数字的运算结果*/push_od(od,result);/*将结果压入od栈中*/*此while循环结束后，计算表达式结束，结果存放在od栈的栈顶*/result=top_od(od);/*从od栈中取出计算结果*/printf(中缀表达式:);/*提示信息*/puts(inorder);

22、/*输出中缀表达式*/printf(结果=%f,result);/*输出结果*/printf(n按任意键退出!);/*提示信息*/四、运行结果图4 中缀转后缀算法运行结果图图5 中缀表达式直接计算算法运行结果图五、遇到的问题及解决这部分我主要遇到了如下两个问题，其内容与解决方法如下所列：l 当我基本将我的思路转为程序并编译通过后，我随意的输入几个算式，有些式子得 出的结果正确，而有的却出现错误。如式子为：9.0*(7+8)的结果正确，而当式子为9*12-5或者7/2-3时就会出错。解决方法：为了发现问题的出处，我又连续试了好几个式子，并亲自计算结果，有些式子的结果很奇怪。其中一些式子本来应该是

23、正值的结果却出现了负值。后来我发现如果式子很短，并且只有加号和乘号就不会出错，于是我就用两个简单的式子验证每个运算符，在验证减号时：7-3得出了-4的答案。于是猜想可能是运算顺序搞反了。接着我又试了试7/3和7%3，得出的结果是0和3。这就验证了我的猜想，于是我就开始检查我的代码，因为在程序中我运用自己建的一个运算函数来进行运算。我就将运算函数中两个数的位置前后对调。结果发现，式子的运算结果正常了，得到了需要的答案。可是还是没弄明白原因，于是我就看了看pop出这些数的数栈，突然想起栈是有调换数的顺序的功能的，先进栈的数后出来，而我却把先pop出来的数赋在运算符前，后pop出来的数放在运算符后面，所以出现了