河南工业大学实验报告
课程名称 编译原理 _ 实验项目 实验三 逆波兰式的产生及计算 院 系 信息科学与工程学院 专业班级 计科F1505班 姓 名 李 杰 学 号 201516010118 指导老师 阎 娟 日 期 2018.5.7 批改日期 成 绩
一.实验目的
1． 深入理解算符优先分析法
2． 掌握FirstVt和LastVt集合的求法有算符优先关系表的求法 3． 掌握利用算符优先分析法完成中缀表达式到逆波兰式的转化
二.实验内容及要求
将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。 程序输入/输出示例： 输出的格式如下：
(1)逆波兰式的生成及计算程序，编制人：姓名，学号，班级 (2)输入一以#结束的中缀表达式(包括+—*/（）数字#)：在此位置输入符号串如(28+68)*2# (3)逆波兰式为：28&68+2* (4)逆波兰式28&68+2*计算结果为192 备注：(1)在生成的逆波兰式中如果两个数相连则用&分隔，如28和68，中间用&分隔； (2)在此位置输入符号串为用户自行输入的符号串。
注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、数字，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；
3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；
三.实验过程
1将一个普通的中序表达式转换为逆波兰表达式的一般算法 ○
(1)首先，需要分配2个栈，栈s1用于临时存储运算符（含一个结束符号），此运算符在栈内遵循越往栈顶优先级越高的原则；栈s2用于输入逆波兰式，为方便起见，栈s1需先放入一个优先级最低的运算符，在这里假定为'#'；
(2)从中缀式的左端开始逐个读取字符x，逐序进行如下步骤：
1.若x是操作数，则分析出完整的运算数（在这里为方便，用字母代替数字），将x直接压入栈s2；
2.若x是运算符，则分情况讨论： 若x是'('，则直接压入栈s1；
若x是')'，则将距离栈s1栈顶的最近的'('之间的运算符，逐个出栈，依次压入栈s2，此时抛弃'('；
若x是除'('和')'外的运算符，则再分如下情况讨论： 若当前栈s1的栈顶元素为'('，则将x直接压入栈s1；
若当前栈s1的栈顶元素不为'('，则将x与栈s1的栈顶元素比较，若x的优先级大于栈s1栈顶运算符优先级，则将x直接压入栈s1。否者，将栈s1的栈顶运算符弹出，压入栈s2中，直到栈s1的栈顶运算符优先级别低于（不包括等于）x的优先级，或栈s2的栈顶运算符为'('，此时再则将x压入栈s1;
(3)在进行完(2)后，检查栈s1是否为空，若不为空，则将栈中元素依次弹出并压入栈s2中（不包括'#'）；
(4)完成上述步骤后，栈s2便为逆波兰式输出结果。但是栈s2应做一下逆序处理，因为此时表达式的首字符位于栈底；
核心算法流程图
输入一个中缀式表示的简单运算表达式
‘#’入栈
x=当前输入符号 是 x是数字吗? 否 栈顶运算符优先级低于x吗? 是 对数字进行处理，形成一个数字串 将向前看符号入栈 栈顶运算符出栈 是 栈顶是’(‘且x为’）吗 否 程序结束 是 否 栈顶运算符与x优先级相等吗? 否 栈顶运算符优先级高于x吗 否 出错处理 是 将栈顶运算符弹出，且输出
2程序思路 ○
设计trans()函数完成将算术表达式转换为后缀表达式的功能，compvalue()函数计算后缀表达式的值，由于直接在函数里面进行输入输出，而且后缀表达式定义为了全局变量，所以没有参数的传递，函数直接没有直接的联系，无返回值，两个函数都定义为void类型。
然后直接在main函数里面调用这两个函数，完成将算术表达式转换为后缀表达式并计算的功能。
3数据结构 ○
全局变量：char ex[max]; /*存储后缀表达式*/
4函数设计 ○
/*将算术表达式转化为后缀表达式*/
void trans(){
char str[max]; /*存储原算术表达式*/ char stack[max]; /*作为栈使用*/
char ch;
int sum,i,j,t,top=0;
printf(\逆波兰式的生成及计算程序，编制人：李杰，201516010118，计科1505\\n\\n\printf(\printf(\ 输入一个求值的表达式，以#结束。 *\\n\printf(\printf(\算术表达式：\
i=0; /*获取用户输入的表达式*/ do{
i++;
scanf(\
}while(str[i]!='#' && i!=max); t=1;i=1; ch=str[i];i++; while(ch!='#'){
switch(ch){
case '(': /*判定为左括号*/
top++;stack[top]=ch; break; while(stack[top]!='('){ } top--; break;
sum=i;
case ')': /*判定为右括号*/ ex[t]=stack[top];top--;t++;
case '+': /*判定为加减号*/ }
}
while(top!=0){ } ex[t]='#';
printf(\原来表达式：\for(j=1;j printf(\ex[t]=stack[top];t++;top--; case '-': while(top!=0&&stack[top]!='('){ } top++;stack[top]=ch; break; ex[t]=stack[top];top--;t++; case '*': /*判定为乘除号*/ while(stack[top]=='*'||stack[top]=='/'){ } top++;stack[top]=ch; break; ex[t]=stack[top];top--;t++; case '/': case ' ':break; default:while(ch>='0'&&ch<='9'){ /*判定为数字*/ } ch=str[i];i++; ex[t]=ch;t++; ch=str[i];i++; i--; ex[t]=' ';t++; } printf(\后缀表达式：\ for(j=1;j printf(\ /*计算后缀表达式的值*/ void compvalue(){ float stack[max],d; /*作为栈使用*/ char ch; int t=1,top=0; /*t为ex下标，top为stack下标*/ ch=ex[t];t++; switch(ch){ while(ch!='#'){ case '+': stack[top-1]=stack[top-1]+stack[top]; top--; break; stack[top-1]=stack[top-1]-stack[top]; top--; break; stack[top-1]=stack[top-1]*stack[top]; top--; break; case '-': case '*': case '/': } if(stack[top]!=0) } printf(\计算结果:%g\\n\ stack[top-1]=stack[top-1]/stack[top]; else{ printf(\除零错误!\\n\ exit(0); /*异常退出*/ } ch=ex[t];t++; } top--; break; d=0; while(ch>='0'&&ch<='9'){ } top++; stack[top]=d; d=10*d+ch-'0'; /*将数字字符转化为对应的数值*/ ch=ex[t];t++; default: 5测试结果 ○正常输入 出错处理 四.实验总结（心得） 1,实验体会 程序较复杂，需要利用到程序设计语言的知识和大量编程技巧，逆波兰式的生成是算符优先分析法的应用，是一种较实用的分析法，通过这个练习可大大提高软件开发能力。实验之前一直不知道为什么要将看似简单的中序表达式转换为复杂的逆波兰式？实验时查阅资料才知道这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。 2.思考部分 虽然完成了基本功能，但还存在某些问题，对输入字符串没进行判断及出错处理，输入字母会直接使程序结束。谈到字母，又感觉可以进一步完善程序，程序应该具有普遍性，不仅仅只是能求数字的逆波兰式，对字母也应同样可以。
计科1505-河南工业大学--编译原理实验三
