编译原理(逆波兰表达式)C语言版

课程名称：编译原理实验项目：后缀表达式的实现姓名：专业：班级：学号：计算机科学与技术学院20 年月日实验名称：消去C程序中的注释一、实验目的1、为了更好的配合《编译原理》有关词法分析章节的教学。

2、加深和巩固学生对于词法分析的了解和掌握。

3、使学生通过本实验能够初步的了解和掌握程序词法分析的整个过程。

4、提高学生的上机和编程过程中处理具体问题的能力。

二、实验要求设计、编制并调制一个程序，将中缀表达式改写为后缀表达式。

掌握中间语言的转换方法。

功能可以包括：1.后缀表达式求值后缀表达式也叫逆波兰表达式，其求值过程可以用到栈来辅助存储。

假定待求值的后缀表达式为：6 5 2 3 + 8 * + 3 + *，则其求值过程如下：1）遍历表达式，遇到的数字首先放入栈中，此时栈如下所示：2）接着读到“+”，则弹出3和2，执行3+2，计算结果等于5，并将5压入到栈中。

3）读到8，将其直接放入栈中。

4）读到“*”，弹出8和5，执行8*5，并将结果40压入栈中。

而后过程类似，读到“+”，将40和5弹出，将40+5的结果45压入栈...以此类推。

最后求的值288。

2.中缀表达式转后缀表达式规则：中缀表达式a + b*c + (d * e + f) * g，其转换成后缀表达式则为a b c * + d e * f + g * +。

转换过程需要用到栈，具体过程如下：1）如果遇到操作数，我们就直接将其输出。

2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。

3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。

注意，左括号只弹出并不输出。

4）如果遇到任何其他的操作符，如（“+”，“*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。

弹出完这些元素后，才将遇到的操作符压入到栈中。

有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "。

逆波兰表达式逆波兰表达式表达式⼀般由操作数(Operand)、运算符(Operator)组成，例如算术表达式中，通常把运算符放在两个操作数的中间，这称为中缀表达式(Infix Expression)，如A+B。

波兰数学家Jan Lukasiewicz提出了另⼀种数学表⽰法，它有两种表⽰形式：把运算符写在操作数之前，称为波兰表达式(Polish Expression)或前缀表达式(Prefix Expression)，如+AB；把运算符写在操作数之后，称为逆波兰表达式(Reverse Polish Expression)或后缀表达式(Suffix Expression)，如AB+；其中，逆波兰表达式在编译技术中有着普遍的应⽤。

算法：⼀、将中缀表达式转换成后缀表达式算法：1、从左⾄右扫描⼀中缀表达式。

2、若读取的是操作数，则判断该操作数的类型，并将该操作数存⼊操作数堆栈3、若读取的是运算符(1) 该运算符为左括号"("，则直接存⼊运算符堆栈。

(2) 该运算符为右括号")"，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为⽌。

(3) 该运算符为⾮括号运算符：(a) 若运算符堆栈栈顶的运算符为括号，则直接存⼊运算符堆栈。

(b) 若⽐运算符堆栈栈顶的运算符优先级⾼或相等，则直接存⼊运算符堆栈。

(c) 若⽐运算符堆栈栈顶的运算符优先级低，则输出栈顶运算符到操作数堆栈，并将当前运算符压⼊运算符堆栈。

4、当表达式读取完成后运算符堆栈中尚有运算符时，则依序取出运算符到操作数堆栈，直到运算符堆栈为空。

⼆、逆波兰表达式求值算法：1、循环扫描语法单元的项⽬。

2、如果扫描的项⽬是操作数，则将其压⼊操作数堆栈，并扫描下⼀个项⽬。

3、如果扫描的项⽬是⼀个⼆元运算符，则对栈的顶上两个操作数执⾏该运算。

4、如果扫描的项⽬是⼀个⼀元运算符，则对栈的最顶上操作数执⾏该运算。

5、将运算结果重新压⼊堆栈。

c语言逆波兰表C语言逆波兰表达式简介一、什么是逆波兰表达式逆波兰表达式，也被称为后缀表达式，是一种不需要括号来标识操作符优先级的数学表达式表示方法。

在逆波兰表达式中，操作符位于操作数之后，因此也被称为后缀表达式。

二、逆波兰表达式的优势1. 不需要括号，减少了人为输入错误的概率。

2. 操作符的位置固定，使得计算机在计算逆波兰表达式时更加简单高效。

3. 逆波兰表达式可以通过栈来实现计算，使得计算逻辑更加清晰。

三、逆波兰表达式的转换将常见的中缀表达式转换为逆波兰表达式有两种方法：中缀转后缀法和中缀转前缀法。

这里我们主要介绍中缀转后缀的方法。

1. 创建一个空栈和一个空字符串作为结果。

2. 从左到右遍历中缀表达式的每个字符。

3. 如果当前字符是操作数，则直接将其添加到结果字符串中。

4. 如果当前字符是操作符，则判断其与栈顶操作符的优先级：a. 如果栈为空，则直接将操作符入栈。

b. 如果栈不为空，且栈顶操作符的优先级大于等于当前操作符，则将栈顶操作符弹出并添加到结果字符串中，直到栈为空或栈顶操作符的优先级小于当前操作符，然后将当前操作符入栈。

5. 如果当前字符是左括号"("，则直接入栈。

6. 如果当前字符是右括号")"，则将栈中的操作符弹出并添加到结果字符串中，直到遇到左括号为止。

此时将左括号弹出，但不添加到结果字符串中。

7. 遍历完中缀表达式后，将栈中剩余的操作符依次弹出并添加到结果字符串中。

四、逆波兰表达式的计算计算逆波兰表达式可以利用栈来实现。

具体步骤如下：1. 创建一个空栈。

2. 从左到右遍历逆波兰表达式的每个字符。

3. 如果当前字符是操作数，则将其转换为数值并入栈。

4. 如果当前字符是操作符，则从栈中弹出两个操作数进行计算，并将计算结果入栈。

5. 遍历完逆波兰表达式后，栈中只剩下一个元素，即为最终的计算结果。

五、逆波兰表达式的应用逆波兰表达式在编程语言解析、数学计算和计算器等领域有着广泛的应用。

逆波兰表达式求值一、需求分析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)，所以时间的复杂度主要取决于字符串的长度，空间也同样取决于字符串长度。

C语言课程设计之逆波兰表达式//逆波兰表达式（后缀表达式）reverse polish notation//程序实现的功能是将中缀表达式转变为后缀表达式，再求出其值//主要运用的知识点有：isdigit函数，pow函数，system("cls")函数，堆栈，格式的强制转换#include<stdio.h>#include<ctype.h>#include<stdlib.h>#include<math.h>void shift( char notation[]); //中缀表达式转换为后缀表达式的转换函数float calculate(float a[][2],int k); //计算后缀表达式int judge(char notation[]); //判断输入的中缀表达式是否符合要求int grade(char a); //返回运算符的等级void display(float a[][2],int k); //在屏幕上显示后缀表达式//主函数void main(){char notation [100];char choice;do{printf("请输入正确的中缀表达式:\n");printf("例如：2*3+4/3-(2+1)\n");scanf("%s",&notation);if(judge(notation)){shift(notation);}elseprintf("你的表达式有错误，请仔细检查！\n");fflush(stdin);printf("\n你是否需要继续计算（是输入Y/y，否输入其他任意键）\n");scanf("%c",&choice);getchar();system("cls");}while(choice=='Y'||choice=='y');printf("\n程序结束，谢谢使用！\n");}//判定函数int judge(char notation[]){int i,m,num=1,p1=0,p2=0;for(i=0;notation[i]!='\0';i++) //排除表达式外的字符{if(notation[i]!='('&&notation[i]!=')'&&notation[i]!='+'&&notation[i]!='-'&&notation[i]!='*'&&notation[i]!='/'&&!isdigit(notation[i])&&notation[i]!='.') {num=0;return num;}}if(notation[0]=='*'||notation[0]=='/'||notation[0]==')'||notation[0]=='.') //排除第一个字符为*，/，)，.{num=0;return num;}for(i=0;notation[i]!='\0';i++) //排除'+'，'-'，'*'，'/','.'之间的连续出现以及'+'，'-','*'，'/','.'后面直接加')'{if(notation[i]!='('&&notation[i]!=')'&&!isdigit(notation[i])){if(notation[i+1]!='('&&!isdigit(notation[i+1])){num=0;return num;}}if(notation[i]=='('&&(notation[i+1]==')'||notation[i+1]=='.'||notation[i+1]=='*'||notation[i+ 1]=='/')){ //排除'('和')','.','*','/'一起连用num=0;return num;}if(notation[i]==')'&&(notation[i+1]=='('||notation[i+1]=='.'))//排除')'和'('，'.'一起连用{num=0;return num;}}for(i=0;notation[i]!='\0';i++) //小数位不得超过4位{if(notation[i]=='.'&&notation[i+1]!='\0'&&notation[i+2]!='\0'&&notation[i+3]!='\0'&&notation[i+4]!='\0'&&notation[i+5]!='\0'){if(isdigit(notation[i+1])&&isdigit(notation[i+2])&&isdigit(notation[i+3])&&isdigit(notation[i+ 4])&&isdigit(notation[i+5])){num=0;return num;}}}for(i=0;notation[i]!='\0';i++) //排除一个小数中有两个小数点的情况{if(notation[i]=='.'){i++;while(isdigit(notation[i])){i++;}if(notation[i]=='.'){num=0;return 0;}}}for(i=0;notation[i]!='\0';i++) //排除')'后面不可以直接跟数字以及'('前面不可以加数字{if(notation[i]==')'&&isdigit(notation[i+1])){num=0;return num;}if(isdigit(notation[i])&&notation[i+1]=='(' ){num=0;return num;}}for(i=0;notation[i]!='\0';i++) //约束数字的位数一共最多为七位{if(isdigit(notation[i])){m=0; //用来计数，数字的位数为7while(isdigit(notation[i])||notation[i]=='.'){i++;m++;if(notation[i]=='.'){m--;}}if(m>7){num=0;return num;}}}for(i=0;notation[i]!='\0';i++) //'('与')'需要配对存在{if(notation[i]=='(')p1++;if(notation[i]==')')p2++;if(p1!=p2){num=0;return num;}}return num;}//转换函数void shift( char notation[]){char s1[100];s1[0]='#';float s2[100][2]; //第一维放后缀表达式的元素，第二维表示小数点的位数以及是否是运算符int i=0,j=1,k=0,t=0;float sum,num1=0,num2=0; //num1为存储整数位num2为存储小数位while(notation[i]!='\0'){if(i==0&&notation[i]=='+') //第一位为正号的情况{if(isdigit(notation[++i])){num1=0; //整数部分while(isdigit(notation[i])){num1=num1*10+(notation[i]-'0'); //notation[i]-'0'可以将字符转换为整数0~9i++;}num2=0; //小数部分t=0;if(notation[i]=='.'){i++;while(isdigit(notation[i])){num2=float (num2+pow(0.1,++t)*(notation[i]-'0'));i++;}}s2[k++][0]=float(num1+num2);s2[k-1][1]=float(t);}}if(i==0&&notation[i]=='-') //第一位为负号的情况，代码与正号类似{if(isdigit(notation[++i])){num1=0;while(isdigit(notation[i])){num1=(-1)*num1*10+(-1)*(notation[i]-'0');i++;}num2=0;t=0;if(notation[i]=='.'){i++;while(isdigit(notation[i])){num2=float(num2+(-1)*pow(0.1,++t)*(notation[i]-'0'));i++;}}s2[k++][0]=float(num1+num2);s2[k-1][1]=float(t);}}if(isdigit(notation[i])) //当前字符为数字的情况与为正号的情况一样{num1=0;while(isdigit(notation[i])){num1=num1*10+(notation[i]-'0');i++;}num2=0;t=0;if(notation[i]=='.'){i++;while(isdigit(notation[i])){num2=float(num2+pow(0.1,++t)*(notation[i]-'0'));i++;}}s2[k++][0]=float(num1+num2);s2[k-1][1]=float(t);}if(notation[i]=='+'||notation[i]=='-'||notation[i]=='*'||notation[i]=='/'){ //当前的字符为操作符时，如果s1的站定为'('则将字符直接送入s1if(s1[j-1]=='('){s1[j++]=notation[i++];}}if(notation[i]=='+'||notation[i]=='-'||notation[i]=='*'||notation[i]=='/'){ //当前字符为操作符时的普通的情况if(grade(notation[i])>grade(s1[j-1])){s1[j++]=notation[i++];}else{s2[k++][0]=s1[--j];s2[k-1][1]=-1;s1[j++]=notation[i++];}}if(notation[i]=='(') //当前字符为'('的情况{s1[j++]=notation[i++];if(notation[i]=='+') //'('后跟正号的情况{if(isdigit(notation[++i])){num1=0;while(isdigit(notation[i])){num1=num1*10+(notation[i]-'0');i++;}num2=0;t=0;if(notation[i]=='.'){i++;while(isdigit(notation[i])){num2=float(num2+pow(0.1,++t)*(notation[i]-'0'));i++;}}s2[k++][0]=float(num1+num2);s2[k-1][1]=float(t);}}if(notation[i]=='-') //'('后跟负号的情况{if(isdigit(notation[++i])){num1=0;while(isdigit(notation[i])){num1=float((-1)*num1*10+(-1)*(notation[i]-'0'));i++;}num2=0;t=0;if(notation[i]=='.'){i++;while(isdigit(notation[i])){num2=float(num2+(-1)*pow(0.1,++t)*(notation[i]-'0'));i++;}}s2[k++][0]=float(num1+num2);s2[k-1][1]=float(t);}}}if(notation[i]==')') //当前字符为')'的情况{while(s1[--j]!='('){s2[k++][0]=s1[j];s2[k-1][1]=-1;}i++;}}while(j>0&&s1[--j]!='#') //依次将s1中的除了'#'外的所有操作符出栈，相当于最后的扫尾工作{s2[k++][0]=s1[j];s2[k-1][1]=-1;}printf("\n后缀表达式（逆波兰表达式）：\n");display(s2,k-1);printf("\n表达式的值为：\n");sum=calculate(s2,k-1);printf("%7.4f",sum);}//计算函数float calculate(float a[][2],int k){int i,t=0,j=k;float b[100][2],c[100];for(i=k;i>=0;i--){b[i][0]=a[k-i][0];b[i][1]=a[k-i][1];}i=k;while(j>=0){if(b[i][1]!=-1){c[t]=float (b[i][0]);j--;i--;t++;}if(b[i][1]==-1) //每当遇到一个运算符则将栈最上面的两个数出栈进行运算，然后再入栈{if(int(b[i][0])=='+'){c[t-2]=float (c[t-2]+c[t-1]);}if(int(b[i][0])=='-'){c[t-2]=float (c[t-2]-c[t-1]);}if(int(b[i][0])=='*'){c[t-2]=float (c[t-2]*c[t-1]);}if(int(b[i][0])=='/'){c[t-2]= float (c[t-2]/c[t-1]);}j--;i--;t--;}}return c[0]; //运算到最后，栈中的元素即为结果}//等级函数int grade(char a) //按照运算符的优先级{if(a=='#')return 0;if(a=='(')return 1;if(a=='-'||a=='+')return 2;if(a=='*'||a=='/')return 3;if(a==')')return 4;elsereturn 5;}//显示函数void display(float a[][2],int k){int i;for(i=0;i<=k;i++){if(a[i][1]==0)printf(" %d",int(a[i][0]));if(a[i][1]==1)printf(" %7.1f",a[i][0]);if(a[i][1]==2)printf(" %7.2f",a[i][0]);if(a[i][1]==3)printf(" %7.3f",a[i][0]);if(a[i][1]==4)printf(" %7.4f",a[i][0]);if(a[i][1]==-1)printf(" %c",int (a[i][0]));}}算法实现一个表达式E的后缀形式可以如下定义：（1）如果E是一个变量或常量，则E的后缀式是E本身。

逆波兰表达式逆波兰表达式题⼲正常的表达式称为中缀表达式，运算符在中间，主要是给⼈阅读的，机器求解并不⽅便。

例如：3 + 5 * (2 + 6) - 1⽽且，常常需要⽤括号来改变运算次序。

相反，如果使⽤逆波兰表达式（前缀表达式）表⽰，上⾯的算式则表⽰为：- + 3 * 5 + 2 6 1不再需要括号，机器可以⽤递归的⽅法很⽅便地求解。

为了简便，我们假设：只有 + - * 三种运算符每个运算数都是⼀个⼩于10的⾮负整数下⾯的程序对⼀个逆波兰表⽰串进⾏求值。

其返回值为⼀个结构：其中第⼀元素表⽰求值结果，第⼆个元素表⽰它已解析的字符数。

public static int[] evaluate(String x){if(x.length() == 0) return new int[]{0,0};char c = x.charAt(0);if (c >= '0' && c <= '9')return new int[]{c - '0', 1};int[] v1 = evaluate(x.substring(1));int[] v2 = __________________________________;//填空位置int v = Integer.MAX_VALUE;if (c == '+') v = v1[0] + v2[0];if (c == '*') v = v1[0] * v2[0];if (c == '-') v = v1[0] - v2[0];return new int[]{v, 1 + v1[1] + v2[1]};}代码public class _06逆波兰表达式 {// int[]数组中// 其中第⼀元素表⽰求值结果，第⼆个元素表⽰它已解析的字符数。

public static int[] evaluate(String x){if(x.length() == 0) return new int[]{0,0}; //char c = x.charAt(0); //取到⾸字符if (c >= '0' && c <= '9') //如果是数字return new int[]{c - '0', 1};// 如果是下⾯的情况，说明是字符，虽然此处没有else但是所表达的意思就是上⾯if之外的情况，因为上⾯的if没有执⾏的话才能够运⾏到下⼀⾏代码int[] v1 = evaluate(x.substring(1));//这⾥是除去第⼀个字符不要的其他部分，第⼀个字符是运算符int[] v2 = evaluate(x.substring(1+v1[1]));//填空位置，猜测是截取上⼀次没有处理到的部分// v1[1]处理v1消耗的字符数量//int v = Integer.MAX_VALUE;if (c == '+') v = v1[0] + v2[0];if (c == '*') v = v1[0] * v2[0];if (c == '-') v = v1[0] - v2[0];return new int[]{v, 1 + v1[1] + v2[1]};}public static void main(String[] args) {// TODO Auto-generated method stubSystem.out.println(evaluate("-+3*5+261")[0]);}}总结1.观察代码，也是从第⼀个字符开始：如果是数字，那么直接返回；如果不是，说明遇到了⼀个操作符，那么v1从这个操作符的后⼀位字符开始递归，直到遇到数字返回；然后v2再进⾏⼀些操作；最后把v1和v2对应的值对于回溯时最近的那个操作符进⾏运算。

c++程序波兰式、逆波兰式、中缀计算1. 引言1.1 概述在计算机科学和编程领域中，数学表达式的计算是一项基本任务。

而波兰式、逆波兰式和中缀计算是常见的用于表示和计算数学表达式的方法。

这些方法都有各自独特的优势和应用场景。

1.2 文章结构本文将对波兰式、逆波兰式和中缀计算进行详细介绍和分析。

首先，在“2. 波兰式计算”部分，我们将探讨波兰式的定义、原理以及如何将中缀表达式转化为后缀形式。

接下来，在“3. 逆波兰式计算”部分，我们将介绍逆波兰式的定义、原理，以及如何将中缀表达式转化为前缀形式。

最后，在“4. 中缀计算”部分，我们将深入讨论中缀表达式的定义、原理以及如何将其转化为逆波兰式形式。

文章最后，“5. 结论”部分将对整个内容进行总结与分析，并讨论这些方法在实际应用中的优点与局限性。

1.3 目的本文旨在阐述波兰式、逆波兰式和中缀计算的概念、原理以及它们在实际应用中的优缺点。

读者将通过本文了解到这些不同的表达式形式如何表示和计算数学表达式，并能根据具体需求选择合适的方法进行计算。

无论是初学者还是有一定编程经验的人，本文都将为他们提供一个全面而清晰的介绍，帮助他们更好地理解和应用波兰式、逆波兰式和中缀计算。

2. 波兰式计算:2.1 定义和原理:波兰式（Polish Notation）是一种用前缀表达式表示数学运算的方法。

在波兰式中，操作符位于操作数之前，通过这种形式来消除了括号对优先级的影响。

例如，表达式"3 + 4" 可以用波兰式表示为"+ 3 4"。

波兰式的原理是利用栈这一数据结构进行计算。

我们将表达式从右到左遍历，如果遇到一个数字，则将其压入栈中；如果遇到一个操作符，则弹出栈顶的两个数字进行计算，并将结果再次压回栈中。

重复这个过程直到整个表达式被处理完毕，并返回最终结果。

2.2 转化为后缀表达式:要将中缀表达式转化为后缀表达式（也称为逆波兰式），我们可以使用以下步骤：1. 创建一个空栈和一个空结果列表。

内蒙古工业大学信息工程学院实验报告课程名称：编译原理实验名称：语法制导把表达式翻译成逆波兰式实验类型：验证性□ 综合性□ 设计性□实验室名称：电力大楼九楼东机房班级：计13-1学号：201320201045姓名：徐铭贝组别：同组人：成绩：实验日期：2016-6一)实验目的进一步掌握语法制导翻译的概念，理解中间语言，设计出错处理程序方法，掌握把表达式翻译成中间语言的算法。

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

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

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

(三)实验要求1．学生课前要认真阅读实验指导，理解实验内容与相关理论知识的关系，并完成预习报告2．用C语言或其它高级语言编写程序3．写出实验报告实验二语法制导把表达式翻译成逆波兰式一、实验名称语法制导把表达式翻译成逆波兰式二、实验目的通过上机实习加深对语法指导翻译原理的理解，进一步掌握语法制导翻译的概念，掌握运算符优先权的算法，将语法分析所识别的表达式变换成中间代码的翻译方法。

三、表达式生成逆波兰式的算法1、初始化△送到运算符栈。

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

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

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

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

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

5、扫描右括号“)”。

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

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

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

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

四、程序清单#include<stdio.h>int jg[30];int fh[30];char fuhao[30][30]; //char fuhao1[30];int fuhao2[30];int number4=0;int number5=0;int bds[30];int number3=0; //表达式char fh1[6]={'(','+','-','*','/','^'}; //关系表int number1=0; //结果int number2=0; //符号int main(){int gx,gx1; //比较关系char aa; //字符int a,b,c=0,sum=0; //平常使用的while(1){c=0;while(1){scanf("%c",&aa);bds[number3]=aa;number3++;if(aa=='#'){for(a=number2-1;a>=0;a--){jg[number1]=fh[a];number1++;}break;}if(aa<='z'&&aa>='a'){jg[number1]=aa;number1++;// printf("aaa\n");}if(aa=='('){fh[number2]=aa;number2++;// printf("bbb\n");}if(aa=='+'||aa=='-'||aa=='*'||aa=='/'||aa=='^') // (<+=-<*=/<^<) {while(1){gx=0;gx1=0;for(a=0;a<6;a++){if(aa==fh1[a])gx=a;if(number2==0){break;}if(fh[number2-1]==fh1[a])gx1=a;}if(number2==0){fh[number2]=aa;number2++;break;}if(gx==1||gx==2){gx=1;}if(gx1==1||gx1==2){gx1=1;}if(gx==4||gx==3){gx=2;}if(gx1==4||gx1==3){gx1=2;}if(gx1>=gx){if(number2==0){// printf("ge2ge2ge2\n");fh[number2]=aa;number2++;break;}// printf("gege\n");jg[number1]=fh[number2-1];// printf("%c\n",fh[number2-1]);fh[number2-1]='\0';number1++;number2--;continue;}else{// printf("ge1ge1\n");fh[number2]=aa;number2++;break;}}}if(aa==')'){// printf(")))\n");for(a=number2-1;a>=0;a--){if(fh[a]=='('){fh[a]='\0';number2--;break;}else {jg[number1]=fh[a];number1++;fh[a]='\0';number2--;}}}}for(a=0;a<number1;a++){printf("%c",jg[a]);}printf("\n");for(a=0;a<number3-1;a++){if(bds[a]<='z'&&bds[a]>='a')if(bds[a+1]<='z'&&bds[a+1]>='a') {fuhao[number4][number5]=bds[a];number5++;}else{fuhao[number4][number5]=bds[a];fuhao2[number4]=number5+1;number5=0;fuhao1[number4]='a'+number4;number4++;}}printf("从前到后依次为:\n");for(a=0;a<number4;a++){printf("%c:::%s\n",fuhao1[a],fuhao[a]);}for(a=0;a<number4;a++){printf("%c",fuhao1[a]);sum=sum+fuhao2[a];for(;(jg[sum]<='z'&&jg[sum]>='a')!=1;sum++) { if(sum>=number1){break;}printf("%c",jg[sum]);}}printf("\n");for(a=0;a<30;a++){jg[a]='\0';fh[a]='\0';for(b=0;b<30;b++){fuhao[a][b]='\0';}}number1=0;number2=0;number3=0;number4=0;number5=0;sum=0;}return 0;}五、算法思想有三个数组分别存放的是符号、变量、优先级、之后输入字符，进行判断是什么东西，之后再对他们进行进出符号，变量直接进，判断优先级（老师上课所讲的逆波兰式如何生成），最后显示出其逆波兰式。

逆波兰式include<stdio.h>#include<math.h>#define max 100char ex[max]; /*存储后缀表达式*/void trans(){ /*将算术表达式转化为后缀表达式*/char str[max]; /*存储原算术表达式*/char stack[max]; /*作为栈使用*/char ch;int sum,i,j,t,top=0;printf("*****************************************"n");printf("*输入一个求值的表达式，以#结束。

*"n");printf("******************************************"n");printf("算数表达式：");i=0; /*获取用户输入的表达式*/do{i++;scanf("%c",&str[i]);}while(str[i]!='#' && i!=max);sum=i;t=1;i=1;ch=str[i];i++;while(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++;ch=str[i];i++;}i--;ex[t]='#';t++;}ch=str[i];i++;}while(top!=0){ex[t]=stack[top];t++;top--;}ex[t]='#';printf(""n"t原来表达式：");for(j=1;j<sum;j++)printf("%c",str[j]);printf(""n"t后缀表达式：",ex);for(j=1;j<t;j++)printf("%c",ex[j]);}void compvalue(){ /*计算后缀表达式的值*/ float stack[max],d; /*作为栈使用*/char ch;int t=1,top=0; /*t为ex下标，top为stack下标*/ch=ex[t];t++;while(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;if(stack[top]!=0)stack[top-1]=stack[top-1]/stack[top];else{printf(""n"t除零错误!"n");exit(0); /*异常退出*/}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++;}printf(""n"t计算结果:%g"n",stack[top]);}main(){trans();compvalue();}。