《表达式运算算法的实现》由会员分享，可在线阅读，更多相关《表达式运算算法的实现（16页珍藏版）》请在金锄头文库上搜索。
1、专 业： 班 级： 指导教师： 姓 名： 学 号： 目 录一、设计思想.01二、算法流程图.01三、源代码.04四、运行结果.12五、遇到的问题及解决.13六、心得体会.1400一、设计思想（1）先将中缀表达式转化为后缀表达式，再通过计算后缀表达式求表达式的值。第一遍扫描中缀表达式，需要一个运算符栈和一个数组。运算符栈用来存放运算符，数组用来存放转换成的后缀表达式。首先将中缀表达式挨个扫描。如果是数字，则直接放在后缀表达式数组中，依次存放。如果扫描到的是运算符，则按照以下规则存放：栈空时，任何运算符可直接入栈。栈不空是，如果栈中运算符的优先级高于或等于将要放入栈中的运算符的优先级，则将栈中运算
2、符出栈，放入后缀表达式数组中，直到栈中运算符优先级低于将要放入栈中的运算符的优先级，此时将此运算符放入运算符栈中。如果遇到左括号，则直接将左括号入栈，左括号入栈后优先级最低，其他运算符可直接放入。如果遇到右括号，则将运算符栈中的运算符依次取出放到后缀表达式数组中，直到遇到左括号为止，此时将左括号从栈顶删除。按此方法，直到后缀表达式转换成功。第二遍扫描后缀表达式，此时需要一个数栈。扫描时如果遇到数字，则直接放到数栈中。如果遇到运算符，则将数栈中两个数取出，先取出的放在运算符后面，后取出的放在运算符前面，进行运算符运算。将运算的结果放入栈中。之后接着扫描后缀表达式。另外因为运算数的位数不一定而且还
3、有小数点，所以在扫到一个数时要判断这个数的位数，将这个完整的运算数字符串整个取出，这需要用到一个辅助索引。当栈中只有一个数字时，这个数字就是我们要求的表达式的值。（2）直接计算表达式的值。这种方法需要两个栈，一个运算符栈，一个数栈。只需扫描一遍中缀表达式，边运算边入栈。当扫描到的为数字是，将其放入数栈中，然后扫描下一个字符。如果扫描到的是运算符，栈空时，任何运算符可直接入栈。栈不空是，如果栈中运算符的优先级高于或等于将要放入栈中的运算符的优先级，则将栈中运算符出栈，并从数栈中取出两个数，先取出的放在后面，后取出的放在前面，进行运算符运算，得出结果后，将其放入数栈中。如果栈顶运算符优先级依然高于
4、或等于将要入栈的运算符优先级，仍然进行以上操作，直到栈顶运算符低于将要放入栈中的的运算符的优先级，此时将该运算符入栈。如果扫描到的是左括号，则直接将其入栈。如果扫描到的是右括号，则将栈顶运算符取出，进行以上运算，直到栈顶为左括号，此时将栈顶左括号删除即可，然后将运算结果放入数栈中。当中缀表达式扫描完，并且运算符栈中全部出栈，数栈中只剩一个数字时，即为运算结果。另外因为运算数的位数不一定而且还有小数点，所以在扫到一个数时要判断这个数的位数，将这个完整的运算数字符串整个取出，这需要用到一个辅助索引。二、算法流程图图 1 是从中缀表达式转为后缀表达式并对后缀表达式进行计算的算法流程图，图中所有图形都
5、是长方形，按箭头顺序依次执行。其中如果箭头向下方向有分叉，则箭头左侧长方形代表“是” ，右侧代表“否” 。图 2 是中缀表达式直接计算的算法流程图。按箭头方向执行。图中如果遇到选择类型的语句，则在箭头有分叉的下一行语句中先声明了选项，然后与后面语句逗号隔开。01具体流程图如下：中缀表达式扫描完毕运算符栈中元素全部输出放入后缀表达式数组 explen中从后缀表达式中取元素 ch=expt,t+是否为数存入数栈中 从数栈中取出两个数进行运算符运算，得出结果放入数栈输出栈里最终栈顶元素即为所求结束ch 是否为（运算符栈为空或者栈运算符优先级低于 ch 优先级将 ch 放入运算符栈中将栈顶运算符出栈放
6、入后缀表达式中，直到栈顶元素优先级低于 ch 优先级，此时将 ch 入栈将 ch 入栈 将操作符栈中元素取出放入后缀表达式中，直到栈顶元素为（用户输入表达式将表达式赋给 strlen构造运算符栈和数栈扫描中缀表达式 ch=stri,i+ch 是否为数将 ch 直接放入后缀表达式数组中ch 是否为+-*/%02图 1 中缀转后缀再计算算法流程图图 2 中缀表达式直接计算算法流程图栈顶元素是否为（是，pop 出左括号操作符栈是否为空不是，取出数栈中两个数，计算后存入数栈为空，取出数栈中的数作为返回值不为空，取出数栈中两个数，计算后存入数栈，作为返回值得到存放中缀表达式的数组运算符，与栈顶比较优先级
7、操作符，判断是运算符还是括号数字或小数点，截取子串并将其转换成 double型存入数栈中判断字符类型依次取出数组中的每个字符右括号，取出栈顶元素左括号，直接入操作符栈判断是哪个括号入操作符栈不高于栈顶，取出数栈中两个数，计算后存入数栈结束03三、源代码下面给出的是用中缀表达式转换为后缀表达式再进行计算的算法实现的程序的源代码：#include/导入要用的包#include#include#define len 1000 struct opnodechar datalen; int top; op;/定义字符栈struct odnodeint top;float datalen;od;/定义数栈
8、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-;/存放后缀表达式的数组添加元素op.top+;op.dataop.top=ch;
9、/入栈break;case*: /判断是否是*、/、%case/: case%:while(op.dataop.top=*|op.dataop.top=/|op.dataop.top=%)04expt+=op.dataop.top-;/栈顶元素为*或/，存放后缀表达式的数组添加元素op.top+;op.dataop.top=ch;/入栈break;case(: op.top+;op.dataop.top=ch;break;/扫描若是(,入栈case): while(op.dataop.top!=()/不是左括号出栈expt+=op.dataop.top-;/栈顶元素不为(，出栈op.top-;
10、/(出栈break;case=:break;default: while(ch=0&ch=0&ch#include #include /*包含库函数*/#define MAX 100 /*定义栈的最大长度*/struct opnode /*声明 op 栈*/char strMAX;int top_op;struct odnode /*声明 od 栈*/double numMAX;int top_od;void push_op(struct opnode *op,char c) /*定义 op 栈的进栈函数*/if(op-top_op=MAX-1) /*如果栈满，不进行操作*/else /*否则
11、，进行进栈操作*/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,double d) /*定义 od 栈的进栈函数*/if(od-top_od=MAX-1) /*如果栈为满，不进行操作*/else /*否则，进行进栈操作*/od-top_o
12、d+;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 语句判断*/case (:return 1;break;case ):return 1;break;08case +:return 1;break
13、;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;break; /*#作为栈底元素*/case ):return 0;break; /*如果是#或)，返回 0*/case
14、(: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) /*计算两个浮点数的运算结果*/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/
