中缀转后缀表达式计算报告

《中缀转后缀表达式计算报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一、设计思想01二、算法流程图02三、源代码04四、运行结果14五、遇到的问题及解决16六、心得体会16一、设计思想(1)中缀表达式转后缀表达式并计算创建一个数组存储输入的计算表达式。另创建一个数组储存将要生成的后缀表达式。创建一个栈储存操作符。对已存储的表达式数组扫描。判断当前节点，如果是操作数或'，直接加入后缀表达式中，如果是操作符，则比较前一个操作符与当前操作符的优先级。如果前一个操作符的优先级较高，则将前一个操作符加入后缀表达式屮，否则将操作符压入操作符栈。如果遇到左括号’(‘，直接入栈；如果遇到右括号’)'，则在操作符栈中反向搜索，直到遇到兀配的左括号为止

2、，将中问的操作符依次加到后缀表达式中。当执行完以上操作，发现栈中仍有剩余操作符，则将操作符依次加到后缀表达式中。此吋中缀表达式已经转换成了后缀表达式。对后缀表达式进行计算。如果后缀表达式为大于0小于9的字符，则将它转换成浮点型数据并存入数栈屮。如果遇到操作符，则从数栈中提取两个数，进行相应的运算。依次进行下去，当没有运算符是，运算结束得到最后的结果。(2)直接表达式求值创建一个数组存储输入的计算表达式。创建两个栈，一个字符型的栈，一个双精度型的栈。分别用来存储字符和数。对已存储的表达式数组扫描。判断当前节点，如果是操作数和’，将字符型的操作数转换为浮点型的数后存入操

3、作数栈。如果是操作符则判断操作符的优先级。如果字符栈中已存储符号的优先级小于要存入的字符的优先级，则直接让字符入操作符栈。如果字符栈中已存储符号的优先级大于或等于要存入的字符的优先级，则取出操作符栈中的一个字符和操作数栈中的两个数进行计算，然后将结果存入操作数栈屮，同上进行下去，直到字符栈屮已存储符号的优先级小于要存入的字符的优先级时，将操作符存入操作符栈中。当遇到左括号'(‘，将左括号直接存入操作符栈屮。当遇到右括号')’，则在操作符栈屮反向搜索，并且每搜到一个字符就在操作数栈中取两个数进行相应的计算。然后，将运算结果存入到操作符栈中。如此进行下去，直到遇到左括号

4、结束。将左括号从栈中取出。最后，如果操作符栈中还有符号，就从操作符栈顶开始将操作符取出并从操作数栈顶开始取出两个数字进行计算，将结果存入操作数栈中。重复上述操作直到操作符栈中没有操作符，得到运算结果。二.算法流程图第一种算法：先将屮缀表达式转化为后缀表达式，然后计算后缀表达式流程图为：川门输人业臥wnsi^iiinAIF//.Mill若为&A►轨业为用点故人丘否图i中缀表达式转化为后缀表达式再计算的流程图第二种算法：直接表达式计算出结果的流程图为:若为括号右括号从符号栈取出操作符,从数栈取出两个数1f计算结果入数字栈是取出左括号左括号看栈顶开始分別建立操作费栈和数值

5、栈用户输入表达式若为数字或小数点若为操作符优先级低与栈顶操作彳校优先入操作符栈V优先级高▼从符号栈取出操作符,从数栈取出两个数计算结果入数字栈I进入数值栈断字符串全部打是▼图2百接计算出结果的流程图/*定义操作符类型*//*字符*//*字符优先级*//*定义操作符栈类型引/*栈内元素的个数*//*操作符栈初始化pKi数引/*操作符栈出栈函数*//*如果栈为空则结束操作*//*取出栈顶元素*//*操作符栈入栈函数*/严操作符栈看栈顶函数引/*如果栈为空则结束操作*/三、源代码1.下血给出的是用先将中缀表达式转化为后缀表达式，然后计算后缀表达式算法实现的程序的源代码：#

6、include#include#inc1udctypedefstruct{charop;intlevel;JOpNodc;typedefstruct{OpNodeop[1001;inttop;intsize;)OpStack;voidinit(OpStack*st){st->size=();st->top=0;)OpNodepop(OpSiack*a){if(a->sizc==0)Iexit(-l);}a->size-;returna->op[—(a->top)];}voidpush(OpStack*a,Op

7、Nodeop){a->size++;a->op[(a->top)++]=op;}OpNodepeek(OpStack*a){if(a->size==0){printf("OpStackisemptyH);exit(-l);}typedefstruct/*定义数值栈类型勺doublenum[l()()];/*栈顶下标*/inttop;intsize;}NutnStack;代数值栈初始化函数卸voidinit2(NumStack*st)st->sizc=0;st->top=0;doublepop2(NumStack*a)/*数值栈出栈函数引if(a->size=