逆波兰表达式实验报告

实验报告成绩：指导教师审核（签名）：年月预习报告实践二语法制导把表达式翻译成逆波兰式(一)实验目的进一步掌握语法制导翻译的概念，理解中间语言，设计出错处理程序方法，掌握把表达式翻译成中间语言的算法。

(二)实验内容1．从左到右扫描中缀表达式，经语法分析找出中缀表达式出现的错误并给出错误的具体位置和类型。

一个运算符栈存放暂时不能出现的运算符，逆波兰区存放逆波兰表达式。

2．测试所编程序，给出正确和错误的结果。

(三)实验要求1．学生课前要认真阅读实验指导，理解实验内容与相关理论知识的关系，并完成预习报告2．用C语言或其它高级语言编写程序3．写出实验报告实验理解：表达式生成逆波兰式的算法1、初始化△送到运算符栈。

2、扫描左括号“（”，把△送到运算符栈。

3、扫描到变量，把它送到逆波兰区。

4、扫描到运算符（1）栈内运算符比较a.栈内运算符>=栈外运算符，把栈内运算符送到逆波兰区。

b.栈内运算符<栈外运算符，把栈外运算符入栈。

( 2 ) 栈内是△把运算符入栈。

5、扫描右括号“)”。

( 1 )栈内是运算符，把栈内运算符送到逆波兰区。

( 2 )栈内是△则△退栈，读入下一个字符。

6、扫描到#（结束符）( 1 )栈内是运算符，把栈内运算符送到逆波兰区。

( 2 )栈内是△结束，否则继续分析。

表达式生成逆波兰式算法的流程图预编译程序：include <stack>#include <deque>#include <string>#define Max 100main(){char str[Max],exp[Max],stack[Max],ch;/*定义表达式区、逆波兰区和运算符栈*/ /*char str[100];*/int i=0,j=0,t=0,top=0;printf("IN:");scanf("%s",str); /*将表达式送入表达式区*/printf("\n");ch=str[i];i++;while(ch!='#') /*判断是否是表达式结束符*/{if(ch>='a' && ch<='z') /*如果是操作数,把它送入逆波兰区*/{exp[t]=ch;t++;}else if(ch=='(') /*如果是左括号，把它送入运算符栈*/{top++;stack[top]=ch;}else if(ch==')'){while(stack[top]!='(') /*如果是右括号，把运算符栈的内容送入逆波兰区*/ {exp[t]=stack[top];top--;t++;}top--;}else if(ch=='+' || ch=='-') /*如果是运算符，栈内运算符和栈外运算符进行比较*/ {w hile(top!=0 && stack[top]!='('){exp[t]=stack[top];top--;t++;}top++;stack[top]=ch;}else if(ch=='*' || ch=='/'){while(stack[top]=='*' || stack[top]=='/'){exp[t]=stack[top];top--;t++;}top++;stack[top]=ch;}ch=str[i];i++;}while(top!=0) /*将运算符栈的内容送入逆波兰区*/ {exp[t]=stack[top];t++;top--;}printf("OUT:");for(j=0;j<t;j++) /*打印逆波兰式*/printf("%c",exp[j]);printf("\n");}实验报告成绩：指导教师审核（签名）：年月实验报告一、目的通过上机实习加深对语法指导翻译原理的理解，掌握运算符优先权的算法，将语法分析所识别的表达式变换成中间代码的翻译方法。

HUNAN UNIVERSITY 课程实习报告题目：逆波兰表达式求值学生姓名范舜奕学生学号20100820608专业班级通信6班指导老师吴帆完成日期 2012.04. 07实验二逆波兰表达式求值★问题描述选一个后缀表达式，利用堆栈来计算该表达式的值，同时要效验后缀表达式是否正确★基本要求（1）从键盘中输入一个后缀表达式，该表达式包括加减乘除的操作符，一级正整数作为操作数等（2）用堆栈来表示★输入输出格式输入：在字符界面上输入一个后缀表达式，其中两相邻操作数之间利用空格隔开。

以“#”表示结束。

输出：如果该后缀表达式正确，那么在字符界面上输出其结果，计算结果小数点后面保留两位有效数字。

如果不正确，请在字符界面上输出表达式错误提示★测试用例输入：2 3 * 1 -#输出：5★设计思路◆为了测试需要，应以浮点数存储输入和输出，利用堆栈来实现算法。

栈的抽象数据类型的定义如下：ADT Stack {数据对象：D={a i| a i∈ElemSet, i=1,2,...,n, n≥0 }数据关系：R={<a i-1 , a i >| a i-1 ,a i∈D, i=2,...,n}基本操作：InitStack(&S)操作结果：构造一个空栈SDestoryStack(&S)初始条件：栈S已存在操作结果：栈S被销毁Pop（&S，e）初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回其值Push（&S，e）初始条件：栈S存在且非空操作结果：插入元素e为新的栈顶元素StackLength（&S）初始条件：栈S已存在操作结果：返回S的元素的个数，即栈的长度} ADT LinkLiSt◆本程序包含三个基本模块（1）主程序模块：元素进栈、出栈、删除栈顶元素、实现数字元素的运算（2）线性表模块：实现栈的抽象数据类型（3）元素结构单元模块：定义栈每个元素的结构◆算法的基本思想：定义堆栈的抽象数据类型，读取键盘上输入的数据，根据读取的输入调用入栈函数，判断输入的数据是否合法，通过switch_case结构判断输入运算符的种类，转而执行不同的处理代码。

实验三逆波兰表达式的产生及计算一、实验目的非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。

二、实验内容将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。

三、逆波兰表达式的产生及计算实验设计思想及算法◆逆波兰式定义将运算对象写在前面，而把运算符号写在后面。

用这种表示法表示的表达式也称做后缀式。

逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。

◆产生逆波兰式的前提中缀算术表达式◆逆波兰式生成的设计思想及算法(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。

(2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。

(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。

(4)如果不是数字，该字符则是运算符，此时需比较优先关系。

做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。

如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。

倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。

(5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。

运用以上算法分析表达式(a+b*c)*d的过程如下：当前符号输入区符号栈输出区（ a+b*c)*da +b*c)*d (+ *c)*d ( ab c)*d (+ a* )*d (+ abc *d (+* ab) *d (+* abc) *d (+ abc*) d ( abc** abc*+d * abc*+* abc*+dabc*+d(1)构造一个栈，存放运算对象。

(2)读入一个用逆波兰式表示的简单算术表达式。

实验4.1 目标代码生成-逆波兰式一、实验目的结合课堂上理论知识，将算术表达式首先转化为逆波兰式(后缀表达式)，然后再转化为目标代码(即假想栈式汇编代码)，以此来了解编译器工作的原理。

二、实验环境1.常用微机一台。

2.c++编译环境（常见如vc6.0）。

三、实验要求将逆波兰直接转化为目标代码并输出。

不考虑生成的目标代码质量，并且忽略机器的特性的细节。

变量寄存器使用R0-R7，对于MOV指令，左边为源操作数，右边为目的操作数。

对于其他运算指令，目的操作数和源操作数进行运算，结果保存在存储源操作数的寄存器中，如ADD 3 4，汇编代码为MOV 3 R0 ADD 4 R0。

四、实验过程1.实验算法1.1逆波兰式生成算法首先设一个运算符栈，当从左到右扫描一个表达式时，若扫描到运算分量，将其保存在数组中。

若扫描到运算符，若运算符栈为空，则该运算符入栈，若栈不为空，则比较运算符的优先级，若当前运算符优先级小于等于栈顶运算符优先级，则将栈顶运算符保存到数组中，并且出栈，继续比较当前运算符和栈顶符号的优先级。

若当前运算符优先级大于栈顶优先级，则当前运算符入栈。

只要碰到’(‘，就进栈，当表达式已扫描完，将栈中的运算依次存入数组中，并出栈。

最后打印出数组的值，’(‘和’)’不存入数组中，所以不输出。

1.2目标代码生成算法首先设一个运算分量栈，开始扫描生成的逆波兰式。

若扫描的是运算分量，则将运算分量入栈。

若扫描到运算符，则按给定的运算符是几目运算(本程序并没有考虑一目运算符，所有的运算符都是二目)，将运算分量栈中栈顶元素保存在一个字符数组变量中，并出栈，然后将字符串变量和栈顶元素生成该运算符的目标代码。

最后把运算结果的寄存器入栈，直到扫描完逆波兰式。

2.程序主要函数说明(1)string Apoland(string expre):将表达式转化为逆波兰式输出。

(2)int top(string ch):本程序中所使用的寄存器为通用寄存器R0-R7，用单字符@，#，<，>，[，]，{，}来代替8个寄存器入栈，函数返回的是寄存器的号，如R0，@代替其进栈，栈顶为@时，则返回0。

逆波兰表达式求值一、需求分析1、从键盘中输入一个后缀表达式，该表示包括加减乘除等操作符，以及正整数作为操作数等。

2、用堆栈来实现3、测试数据输入：2 3 * 1 – #输出：2 3 * 1 -- =5二、概要设计抽象数据类型需要一个浮点数栈来存储还没有计算的浮点数或者运算的结果。

ADT Stack数据成员：int size; int top; //分别用于存储栈大小、栈顶位置float *listArray;//存储浮点型数字的数组成员函数：bool push(float it);bool pop(float& it);bool isEmpty(); //判断栈为空bool isOne();//判断栈是否只有一个元素算法的基本思想1. 逐一扫描字符串，用ascii码进行判断，如果该字符是数字，则利用x=x*10+str[i]-48将数据由字符类型转换为浮点型数据；2. 如果字符是‘.’，则将‘.’转化为小数点，并将‘.’后的数据转化为小数部分；3. 遇到空格前是数据的，将x押入栈；4. 如果该字符是’+’，’-’，’*’或’/’，判断栈里的元素是否少于两个个，如果少于两个，报错；如果大于等于两个，就弹出两个数据，并进行相应的计算；程序的流程输入字符串，程序对字符串依次扫描。

扫描一位，处理一位。

扫描完成后，判断栈里是不是只有一个数据，若是，得到正确结果；若不是，则表达式出错。

三、详细设计物理数据类型用浮点数类型的栈存储运算中要用的数据，需要入栈、出栈，故设计如下的浮点类型的栈：class Stack{private:int size;int top;float *listArray;public:Stack(int sz=20);~Stack();bool push(float it);//入栈bool pop(float& it);//出栈bool isEmpty();//判断栈是否为空bool isOne(); //判断栈里是否只有且仅有一个元素};成员函数的函数体Stack::Stack(int sz) //栈构造函数{size=sz;top=0;listArray=new float[size]; }bool Stack::push(float it) {if(top==size)return false;listArray[top++]=it;return true;}bool Stack::pop(float& it) {if(top==0)return false;it=listArray[--top];return true;}bool Stack::isEmpty() //判断站是否为空{if(top==0)return true;return false;}bool Stack::isOne(){if(top==1)return true;return false;}Stack::~Stack(){delete listArray;}算法的具体步骤用switch语句实现1. 逐一扫描字符串，用ascii码进行判断，如果该字符是数字，则利用x=x*10+str[i]-48将数据由字符类型转换为浮点型数据；2. 如果字符是‘.’，则将‘.’转化为小数点，并将‘.’后的数据转化为小数部分；3. 遇到空格前是数据的，将x押入栈；4. 如果该字符是’+’，’-’，’*’或’/’，判断栈里的元素是否少于两个个，如果少于两个，报错；如果大于等于两个，就弹出两个数据，并进行相应的计算；算法的时空分析因为入栈、出栈的时间复杂度均为Θ(1)，所以时间的复杂度主要取决于字符串的长度，空间也同样取决于字符串长度。

编译原理实验报告6-逆波兰式的翻译和计算实验6 逆波兰式的翻译和计算一、实验目的通过实验加深对语法指导翻译原理的理解，掌握算符优先分析的方法，将语法分析所识别的表达式变换成中间代码的翻译方法。

二、实验内容设计一个表示能把普通表达式（中缀式）翻译成后缀式，并计算出结果的程序。

三、实验要求1、给出文法如下：G[E]E->T|E+T;T->F|T*F;F->i(E);对应的转化为逆波兰式的语义动作如下：E-> E(1)op E(2) {E.CODE:=E(1).CODE||E(2).CODE||op}E->(E(1)) { E.CODE := E(1).CODE}E->id { E.CODE := id} 2、利用实验5中的算符优先分析算法，结合上面给出的语义动作实现逆波兰式的构造；3、利用栈，计算生成的逆波兰式，步骤如下：1）中缀表达式，从文本文件读入，每一行存放一个表达式，为了降低难度，表达式采用常数表达式；2）利用结合语法制导翻译的算符优先分析，构造逆波兰式；3）利用栈计算出后缀式的结果，并输出；四、实验环境PC微机DOS操作系统或Windows 操作系统Turbo C 程序集成环境或Visual C++ 程序集成环境#include<math.h>using namespace std;#define max 100char ex[max];int n;char GetBC(FILE* fp) {//读取文件的字符直至ch不是空白c har ch;d o {ch = fgetc(fp);} while (ch == ' ' || ch == '\t' || ch == '\n');r eturn ch;}void acquire(FILE* fp){c har str[max];c har stack[max];c har ch;i nt sum, i, j, t, top = 0;i = 0;/*读取一行表达式*/G etBC(fp);i f (feof(fp))return;e lse {fseek(fp, -1L, 1);printf("\n(%d)", n);n++;}d o{i++;str[i] = GetBC(fp);} while (str[i] != ';' && i != max); s um = i;t = 1;i = 1;c h = str[i];i++;w hile (ch != ';'){switch (ch){case '(':top++; stack[top] = ch;break;case ')':while (stack[top] != '(') {ex[t] = stack[top];top--;t++;}top--;break;case '+':case '-':while (top != 0 && stack[top] != '(') {ex[t] = stack[top];top--;t++;}top++;stack[top] = ch;break;case '*':case '/':while (stack[top] == '*' || stack[top] == '/'){ex[t] = stack[top];top--;t++;}top++;stack[top] = ch;break;case ' ':break;default:while (ch >= '0'&&ch <= '9'){ ex[t] = ch;t++;/*ex[ ]中存放逆波兰式 */ch = str[i];i++;/*str[ ]中存放中缀表达式*/ }i--;ex[t] = ',';t++;break;}ch = str[i];i++;}/*当中缀表达式扫描完毕，检查ω栈是否为空，若不空则一一退栈*/w hile (top != 0) {ex[t] = stack[top];t++;top--;}e x[t] = ';';f or (j = 1; j < sum; j++)printf("%c", str[j]);p rintf("\n输出：");f or (j = 1; j < t; j++)printf("%c", ex[j]);}void getValue() {f loat stack[max], d;c har ch;i nt t = 1, top = 0;c h = ex[t];t++;w hile (ch != ';'){switch (ch){case '+':stack[top - 1] = stack[top - 1] + stack[top];top--;break;case '-':stack[top - 1] = stack[top - 1] - stack[top];top--;break;case '*':stack[top - 1] = stack[top - 1] * stack[top];top--;break;case '/':if (stack[top] != 0)stack[top - 1] = stack[top - 1] / stack[top];else{printf("除零错误\n");break;/*异常退出*/}top--;break;/*将数字字符转化为对应的数值*/ default:d = 0;while (ch >= '0'&&ch <= '9') {d = 10 * d + ch - '0';ch = ex[t];t++;}top++;stack[top] = d;}ch = ex[t];t++;}p rintf("\t%g\n", stack[top]);}void main() {F ILE* fp;e rrno_t err;i f ((err = fopen_s(&fp,"C:\\Users\\Administrator\\Desktop\\e xpression.txt", "r")) != NULL){ //以只读方式打开文件，失败则退出程序printf("file can not open!");exit(0);}n = 1;p rintf("逆波兰式的翻译和计算结果如下：\n");w hile (1) {acquire(fp);if (feof(fp)) break;getValue(); }f close(fp);f p = NULL;}实验结果：问题：这次实验较之之前不同，在设计算法与数据结构上花的时间较少，因为之前在数据结构课程里做过使用堆栈完成表达式的计算，也学过中缀式和后缀式，所以代码编得较快，但是其中的算法其实是较复杂的，调试时显得更复杂而编程时我用的是VS，在调试开始时，断点是不能增加的，这样影响了调试的进度，其实之前做实验就注意到了，只是没有特别在意，但这个实验的算法较复杂，断点设得较多，这让我想到使用JAVA，也许使用java开发会更容易，调试的问题也可以解决，主要是使用现在对于C++的熟练程度远不如Java,如果能充分使用类和对象的特点，各种算法的实现将更加有条理，更易读易修改。

编译原理课程实验报告班级学号姓名实验名称逆波兰式的产生一、实验目的：将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。

二、实验要求：输出的格式如下：(1)逆波兰式的生成及计算程序，编制人：姓名，学号，班级(2)输入一以#结束的中缀表达式(包括+—*/（）数字#)：在此位置输入符号串如(28+68)*2#(3)逆波兰式为：28&68+2*(4)逆波兰式28&68+2*计算结果为192备注：(1)在生成的逆波兰式中如果两个数相连则用&分隔，如28和68，中间用&分隔；(2)在此位置输入符号串为用户自行输入的符号串。

注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、数字，结束符#；2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；三、实验过程：（一）准备：1.阅读课本有关章节，2.考虑好设计方案；3.设计出模块结构、测试数据，初步编制好程序。

（1）定义部分：定义常量、变量、数据结构。

（2）初始化：设立算符优先分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；（3）控制部分：从键盘输入一个表达式符号串；（4）利用算符优先分析算法进行表达式处理：根据算符优先分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。

（5）对生成的逆波兰式进行计算。

（二）上课上机：将源代码拷贝到机上调试，发现错误，再修改完善。

第二次上机调试通过。

四、实验结果（1）写出程序流程图（2）给出运行结果。

实验三逆波兰式的产生及计算实验目的：将用中缀式表示的算术表达式转换为用逆波兰式表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。

估计实验时间：1.课余准备15小时；2.上机一次2小时；3.完成实验报告5小时。

输入如下：21+（（42-2）*15+6 ）-18#输出如下：原来表达式：21+（（42-2）*15+6 ）- 18#后缀表达式：21&42&2&-15&*6&++18&-计算结果：609程序流程图：实验源代码：#include <cstdlib>#include <iostream>#include<string>#include<stack>using namespace std;double cast(string& sstr)//将string类型转型为double{double dou=0;for(string::iterator Iter=sstr.begin();Iter!=sstr.end();++Iter){dou=dou*10+(*Iter)-'0';}return dou;}int main(int argc, char *argv[]){stack<double> dou;//存放表达式中的数字stack<char> sta;//存放运算符string str,str1[100],str2;//str1[100]存放后缀表达式cout<<"请输入要计算的表达式：";cin>>str;//原表达式cout<<"原来的表达式是："<<str<<endl;int size=0;string::iterator iter=str.begin();while(iter!=str.end()&&(*iter)!='#')//扫描原表达式中的每一个字符{if((*iter)>='0'&&(*iter)<='9')//如果是数字则存入str2中{str2+=(*iter);}else//如果不是数字{if(str2!="")//如果str2不为空则将其存入后缀表达式{str1[size]=str2;++size;str2="";}if((*iter)!=')')//如果原表达式中字符不是右括号{if((*iter)=='+'||(*iter)=='-'){while(!sta.empty()&&sta.top()!='(')//直到遇到栈里面的左括号前将栈顶元素存入后缀表达式中{str1[size]=sta.top();++size;sta.pop();}}if(!sta.empty()&&((*iter)=='*'||(*iter)=='/')&&(sta.top()=='*'||sta.top()=='/'))//如果当前字符是*或者/且前一个运算符也是*或者/则将前一个运算符存入后缀表达式{str1[size]=sta.top();++size;sta.pop();}sta.push((*iter));//将当前字符压栈}else//如果是右括号{while(sta.top()!='(')//直到遇到栈里面的左括号前将栈顶元素存入后缀表达式中{str1[size]=sta.top();++size;sta.pop();}sta.pop();//将左括号出栈}}++iter;}if(str2!="")//将原表达式最后的数字存入后缀表达式{str1[size]=str2;++size;}while(!sta.empty())//将栈中的运算符全部存入后缀表达式{str1[size]=sta.top();++size;sta.pop();}cout<<"后缀表达式是：";for(int i=0;i!=size;++i){cout<<str1[i]<<'&';if(str1[i]=="+"||str1[i]=="-"||str1[i]=="*"||str1[i]=="/")//一旦遇到运算符则将double栈中的前两个数计算{double dou1=dou.top();dou.pop();double dou2=dou.top();dou.pop();if(str1[i]=="+")dou.push(dou2+dou1);if(str1[i]=="-")dou.push(dou2-dou1);if(str1[i]=="*")dou.push(dou2*dou1);if(str1[i]=="/")dou.push(dou2/dou1);}else//如果是数字则将其存入double栈中dou.push(cast(str1[i]));}cout<<endl;cout<<"计算结果是："<<dou.top()<<endl;system("PAUSE");return EXIT_SUCCESS;}实验结果：。

淮阴工学院编译原理课程设计报告选题名称:逆波兰式的生成2011年6 月24日设计任务书课题名称逆波兰式的生成设计目的通过一周的课程设计，对逆波兰式的生成过程有了深刻的理解。

整体过程是实现对输入合法的中缀表达式进行词法分析、语法分析，并构造相应的逆波兰式，计算逆波兰式的值并输出结果。

达到了巩固理论知识、锻炼实践能力的目的。

实验环境Windows2000以上操作系统，Visual C++6.0以上编译环境任务要求1.对算术表达式进行词法、语法、逆波兰式的分析；2.编写代码，实现逆波兰式的生成；3.撰写课程设计报告；4.参加答辩。

工作进度计划序号起止日期工作内容1 2011.06.20～2011.06.20 理论辅导，搜集资料2 2011.06.21～2011.06.22 编写代码，上机调试3 2011.06.22～2011.06.23 撰写课程设计报告4 2011.06.24~2011.06.25 答辩，完善报告指导教师（签章）：年月日摘要：编译原理旨在介绍编译程序构造的一般原理和基本方法。

内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。

它是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。

为了把理论知识更加牢固地掌握，同时也是为了培养我们的实践能力，安排了这次课程设计。

这次课程设计的主要任务是编程实现对输入合法的中缀表达式进行词法分析、语法分析，并构造相应的逆波兰式，计算逆波兰式的值并输出结果。

逆波兰式也叫后缀表达式，是为了纪念波兰数学家鲁卡谢维奇（Jan Lukasiewicz）而命名的。

比如中缀表达式：A*(B+C)，其后缀表达式为：ABC+*。

后缀表达式的优点是显而易见的，编译器在处理时候按照从左至右的顺序读取逆波兰表达式，遇到运算对象直接压入堆栈，遇到运算符就从堆栈提取后进的两个对象进行计算，这个过程正好符合了计算机计算的原理。

逆波兰式生成程序一、实验的性质、目的和任务1、培养学生初步掌握编译原理实验的技能。

2、验证所学理论、巩固所学知识并加深理解。

3、对学生进行实验研究的基本训练。

二、实验内容掌握语法分析的基本思想，并用高级语言编写逆波兰式生成程序三、实验要求利用逆波兰式生成算法编写程序，将从键盘上输入的算术表达式（中缀表达式）转化成逆波兰式。

四、常用运算符的优先关系如上表所示的优先关系矩阵表示了+，-，*，/，↑，（，）等七种运算符之间的相互优先关系。

“＞、＜、＝”三种符号分别代表“大于”、“小于”、“相等”三种优先关系。

左边的“＝”与右边的“（”之间没有优先关系存在，所以表中为空白。

逆波兰表达式生成算法的关键在于比较当前运算符与栈顶运算符的优先关系，若当前运算符的优先级高于栈顶运算符，则当前运算符入栈，若当前运算符的优先级低于栈顶运算符，则栈顶运算符退栈。

五、程序流程图六、程序源代码#include <iostream> #include <stack>#include <string>using namespace std;int prior(char op){if(op=='+'||op=='-')return 1;if(op=='*'||op=='/')return 2;return 0;}string middletolast(string middle) {stack<char> op;string ans;for(int i=0;i<middle.size();i++) {char c=middle[i];if(c>='0'&&c<='9'){ans.append(1,c);}else{if(c=='(')op.push('(');else{if(c==')'){while(op.top()!='('){ans.append(1,op.top());op.pop();}op.pop();}else{if(op.empty()){op.push(c);}else{if(prior(c)>prior(op.top()))op.push(c);else{while(!op.empty()&&prior(c)<=prior(op.top())){ans.append(1,op.top());op.pop();}op.push(c);}}}}}}while(!op.empty()){ans.append(1,op.top());op.pop();}return ans;}int main(){string mdata,res;cout<<"请输入常规表达式：\n"<<endl;cin>>mdata;res=middletolast(mdata);for(int i=0;i<res.size();i++){if(i==0)cout<<res[i];elsecout<<' '<<res[i];}cout<<endl;return 0;}七、实验结果。