《中缀转后缀表达式计算报告》由会员分享，可在线阅读，更多相关《中缀转后缀表达式计算报告（18页珍藏版）》请在金锄头文库上搜索。
1、目 录一、设计思想.01二、算法流程图.02三、源代码.04四、运行结果.14五、遇到的问题及解决.16六、心得体会.16用两种方式实现表达式自动计算- 1 -一、设计思想（1）中缀表达式转后缀表达式并计算创建一个数组存储输入的计算表达式。另创建一个数组储存将要生成的后缀表达式。创建一个栈储存操作符。对已存储的表达式数组扫描。判断当前节点，如果是操作数或.，直接加入后缀表达式中，如果是操作符，则比较前一个操作符与当前操作符的优先级。如果前一个操作符的优先级较高，则将前一个操作符加入后缀表达式中，否则将操作符压入操作符栈。如果遇到左括号(，直接入栈；如果遇到右括号),则在操作符栈中反向搜索，直到
2、遇到匹配的左括号为止，将中间的操作符依次加到后缀表达式中。当执行完以上操作，发现栈中仍有剩余操作符，则将操作符依次加到后缀表达式中。此时中缀表达式已经转换成了后缀表达式。对后缀表达式进行计算。如果后缀表达式为大于 0 小于 9 的字符，则将它转换成浮点型数据并存入数栈中。如果遇到操作符，则从数栈中提取两个数，进行相应的运算。依次进行下去，当没有运算符是，运算结束得到最后的结果。（2）直接表达式求值创建一个数组存储输入的计算表达式。创建两个栈，一个字符型的栈，一个双精度型的栈。分别用来存储字符和数。对已存储的表达式数组扫描。判断当前节点，如果是操作数和.，将字符型的操作数转换为浮点型的数后存入操
3、作数栈。如果是操作符则判断操作符的优先级。如果字符栈中已存储符号的优先级小于要存入的字符的优先级，则直接让字符入操作符栈。如果字符栈中已存储符号的优先级大于或等于要存入的字符的优先级，则取出操作符栈中的一个字符和操作数栈中的两个数进行计算，然后将结果存入操作数栈中，同上进行下去，直到字符栈中已存储符号的优先级小于要存入的字符的优先级时，将操作符存入操作符栈中。当遇到左括号(，将左括号直接存入操作符栈中。当遇到右括号)，则在操作符栈中反向搜索，并且每搜到一个字符就在操作数栈中取两个数进行相应的计算。然后，将运算结果存入到操作符栈中。如此进行下去，直到遇到左括号结束。将左括号从栈中取出。最后，如果
4、操作符栈中还有符号，就从操作符栈顶开始将操作符取出并从操作数栈顶开始取出两个数字进行计算，将结果存入操作数栈中。重复上述操作直到操作符栈中没有操作符，得到运算结果。2、算法流程图第一种算法:先将中缀表达式转化为后缀表达式，然后计算后缀表达式流程图为：用两种方式实现表达式自动计算- 2 -开始分别建立操作符栈和数值栈用户输入表达式扫描字符串并获取字符判断字符类型若为数字或小数 若为操作符栈是否为空是与栈顶操作符比较优先级否栈顶元素出栈并存入数组高括号类型若为括号看栈顶右括号是否为左括号去掉左括号判断字符串是否全部扫描进入操作符栈左括号低进入数组出栈存入数组 否操作符栈内元素出栈并存入数组得到后缀
5、表达式扫描后缀表达式判断符号类型从数栈取两个数做相应计算结果入栈转化为浮点数入栈是若为操作符 若为数字判断表达式是否扫描结束从数组栈中取出计算结果作为返回值是输出结果否否下一个字符是否为 “ ”是否若是的话把零加入第一个字符是否为 “ ”否若是把零加入图 1 中缀表达式转化为后缀表达式再计算的流程图用两种方式实现表达式自动计算- 3 -第二种算法:直接表达式计算出结果的流程图为：开始用户输入表达式分别建立操作费栈和数值栈扫描字符串并获取字符判断字符类型进入数值栈若为数字或小数点括号类型若为括号入操作符栈左括号是否为左括号看栈顶右括号取出左括号是从符号栈取出操作符 ，从数栈取出两个数计算结果入数
6、字栈否与栈顶操作符比较优先级若为操作符优先级低从符号栈取出操作符 ，从数栈取出两个数优先级高计算结果入数字栈判断字符串是否全部扫描否符号栈是否为空是得到结果将数值栈顶返回是从符号栈取出操作符 ，从数栈取出两个数计算结果入数字栈否图 2 直接计算出结果的流程图用两种方式实现表达式自动计算- 4 -三、源代码1.下面给出的是用先将中缀表达式转化为后缀表达式，然后计算后缀表达式算法实现的程序的源代码：#include #include#includetypedef struct /*定义操作符类型*/char op; /*字符*/int level; /*字符优先级*/OpNode;typedef
7、struct /*定义操作符栈类型*/OpNode op100;int top;int size; /*栈内元素的个数*/ OpStack; void init(OpStack *st) /*操作符栈初始化函数 */st-size=0;st-top=0;OpNode pop(OpStack *a) /*操作符栈出栈函数*/if (a-size=0) /*如果栈为空则结束操作*/exit(-1);a-size-;return a-op-(a-top); /*取出栈顶元素*/void push(OpStack *a,OpNode op) /*操作符栈入栈函数*/a-size+;a-op(a-top
8、)+=op;OpNode peek(OpStack *a) /*操作符栈看栈顶函数 */if (a-size=0) /*如果栈为空则结束操作*/printf(OpStack is emptyn);exit(-1);用两种方式实现表达式自动计算- 5 - return a-op(a-top)-1; /*只得到栈顶元素而不删除*/typedef struct /*定义数值栈类型*/double num100; int top; /*栈顶下标*/int size; NumStack;void init2(NumStack *st) /*数值栈初始化函数 */st-size=0;st-top=0;do
9、uble pop2(NumStack *a) /*数值栈出栈函数*/if (a-size=0) exit(-1);a-size-;return a-num-(a-top); /*得到栈顶的元素值*/void push2(NumStack *a,double num) /*数值栈入栈函数*/a-size+;a-num(a-top)+=num;int main() /*主函数*/void change (char str,char exp); /*声明要用到的各个函数 */double CalResult(char exp); /*声明后缀表达式的计算函数*/char str100,exp100;
10、 /*str 存放算术表达式，exp 存放对应的后缀表达式*/printf(算术表达式为:); gets(str);change(str,exp); /*调用函数将中缀转化为后缀*/printf(后缀表达式为:%sn,exp); printf(运算结果为： %fn,CalResult(exp); /*调用函数计算后缀表达式*/void change (char str,char exp) /*将中缀表达式转化为后缀表达式 */int i=0; /*str 的索引*/int k=0;用两种方式实现表达式自动计算- 6 -char c; /*存放字符串中取出的字符 */OpStack opst;
11、/*定义操作符栈*/OpNode op;OpNode optemp;init( /*初始化操作符栈*/c=stri+;while (c!=0) /*对字符串进行扫描*/if ( (c=0&c=0&c=op.level) /*如果栈顶优先级高*/optemp=pop(expk+=optemp.op; /*将栈顶元素取出存入数组中*/if (opst.size0) /*进行判空操作，栈为空结束*/optemp=peek( elsebreak;push( /*此时栈顶优先级低，入栈*/if(c=*|c=/|c=%) /*如果是 * 或 / 或 % */op.op=c; op.level=2; /*优
12、先级为 2*/if (opst.size=0)push( /*如果此时栈为空直接入栈*/elseoptemp=peek( /*观察栈顶*/while (optemp.level=op.level) /*如果栈顶优先级高*/optemp=pop( /*将栈顶元素取出存入数组中*/expk+=optemp.op;if (opst.size0)optemp=peek( /*进行判空操作，栈为空结束 */elsebreak;push( /*此时栈顶优先级低，入栈*/用两种方式实现表达式自动计算- 8 -c=stri+; /*索引自加检索下一个字符*/while(opst.size!=0) /*最后判断栈如果不为空*/optemp=pop( /*取出栈内元素存入数组中*/expk+=optemp.op;expk=0; /*将 0 作为结尾存入数组*/double CalRes
