编译原理实验三 逆波兰式的产生及计算.doc

实验三 逆波兰式的产生及计算一、实验目的：将用中缀式表示的算术表达式转换为用逆波兰式表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。二、实验内容:1.定义部分：定义常量、变量、数据结构。 2.初始化：设立算符优先分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）； 3.控制部分：从键盘输入一个表达式符号串； 4.利用算符优先分析算法进行表达式处理：根据算符优先分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。 5.对生成的逆波兰式进行计算。三、实验要求：输入如下： 21+（42-2）*15+6 ）-18#输出如下： 原来表达式： 21+（42-2）*15+6 ）- 18# 后缀表达式：21&42&2&-15&*6&+18&- 计算结果：609四、实验源程序：#include#include#define max 100char exmax; void trans() char strmax; char stackmax; char ch; int sum,i,j,t,top=0; printf(请输入一个求值的表达式，以#结束。n); printf(算数表达式：); i=0; /*输入表达式*/ do i+; scanf(%c,&stri); while(stri!=# & i!=max); sum=i; t=1;i=1; ch=stri;i+; while(ch!=#) switch(ch) /*判定为左括号*/ case (: top+;stacktop=ch; /入栈 break; /*判定为右括号*/case ): while(stacktop!=() /栈顶不为(时 ext=stacktop; top-;t+; top-; break; /栈顶为(，退栈/*运算符*/*判定为加减号*/ case +: case -: while(top!=0&stacktop!=() ext=stacktop;top-;t+; /*stack为运算符栈*/ top+; stacktop=ch; break;/*判定为乘除号*/ case *: case /: while(stacktop=*|stacktop=/) ext=stacktop;top-;t+; top+; stacktop=ch; break; case : break;/*判定为数字*/default:while(ch=0&ch=9) ext=ch;t+; /*ex 中存放逆波兰式 */ ch=stri;i+; /*str 中存放中缀表达式*/ i-; ext=&;t+;break; ch=stri; i+; /*当中缀表达式扫描完毕，检查栈是否为空，若不空则一一退栈*/ while(top!=0) ext=stacktop; t+; top-; ext=#; printf(nt原来表达式：); for(j=1;jsum;j+) printf(%c,strj); printf(nt后缀表达式：,ex); for(j=1;j=0&ch=9) d=10*d+ch-0; ch=ext;t+; top+; stacktop=d; ch=ext; t+;