语法制导把表达式翻译成逆波兰式

表达式转换成逆波兰式
早在上世纪20年代，逆波兰式（Reverse Polish Notation，RPN）就出现了。

它的目的是提高计算机程序执行速度，以减少计算机
程序员使用时间，同时提高计算机程序操作的准确性。

因此，在程序
设计中它得到了广泛应用，成为一种基础的数学表达符号。

逆波兰表达式（RPN）指的是把一个表达式按照一定的规则转换
成一种逆波兰的表达式。

这种表达式的每个元素都是单个操作数或操
作符号，操作符放在操作数之前，各操作符号和操作数按照一定次序
跟随在一起。

RPN有许多优势，如解释性强、空间利用率高、更易于扩展和容
错率高等，且不会因为把操作符和操作数放置次序反而影响计算结果。

例如，将一个表达式 sus=(a+b)*c转化成它的逆波兰式即：a b + c * sus =
RPN的算法更加容易理解，它使用的操作数及操作符只有当前字
符的操作数及操作符，而不需要像结构化算法那样维护进入和离开栈
的字符（操作数和操作符）的相关信息。

RPN算法也在某些场合得到广泛的应用，尤其是在使用的机器无
法处理复杂程序时，如小型计算机或一些移动设备。

同时，RPN也是一种被广泛使用的量化计算方法，可以节省时间和精力，提高数学计算
过程的准确性。

总之，逆波兰表达式是一种有效的、普遍应用并且在不同场合用
途十分重要的广泛运用于数学计算中的技术。

它可以消除操作符在表
达式中的优先级差异，将一个复杂的表达式简化为另一个同意义的，
更简洁的表达式，从而提高计算的准确性和速度。

把表达式转换为逆波兰表达式的方法把表达式转换为逆波兰表达式的方法什么是逆波兰表达式？逆波兰表达式（Reverse Polish Notation，简称RPN）是一种数学表达式的表示方法，其中运算符位于操作数的后面，而不是中间。

例如，将中缀表达式 3 + 4转换为逆波兰表达式的结果是 3 4 +。

为什么要使用逆波兰表达式？逆波兰表达式具有以下优点：1.不需要括号：逆波兰表达式由于运算符在操作数的后面，所以不需要括号来定义运算次序。

2.方便计算机计算：逆波兰表达式可以直接由计算机进行计算，减少了计算机解析表达式的复杂性。

3.避免二义性：逆波兰表达式的书写方式清晰明确，没有二义性。

方法一：使用栈实现转换1.初始化一个空栈和一个空列表用于存储转换后的逆波兰表达式。

2.从左到右扫描表达式。

3.如果遇到操作数（数字），则直接添加到逆波兰表达式列表中。

4.如果遇到运算符，按照以下规则处理：–如果栈为空或栈顶为左括号（或无运算符优先级低于当前运算符），则直接将运算符入栈。

–如果栈顶为运算符，并且其优先级大于等于当前运算符，将栈顶运算符出栈并添加到逆波兰表达式列表中，直到栈为空或栈顶为左括号（或无运算符优先级低于当前运算符）为止，然后将当前运算符入栈。

–如果当前运算符为右括号，则将栈顶运算符依次出栈并添加到逆波兰表达式列表中，直到遇到左括号为止。

5.扫描完成后，将栈中剩余的运算符依次出栈并添加到逆波兰表达式列表中。

6.逆波兰表达式列表即为转换后的结果。

方法二：使用递归实现转换1.定义一个递归函数，传入表达式和当前处理位置。

2.判断当前位置处的字符：–如果是数字，则直接返回该数字。

–如果是运算符，则递归调用函数获取左右两个操作数，并根据运算符将其组合成一个逆波兰表达式返回。

–如果是左括号，则继续向后处理直到找到对应的右括号。

3.递归函数返回结果即为转换后的逆波兰表达式。

方法三：使用中缀转后缀的方法1.定义两个栈，一个用于临时存储运算符，一个用于存储转换后的逆波兰表达式。

逆波兰表达式逆波兰表达式表达式⼀般由操作数(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、将运算结果重新压⼊堆栈。

实验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++ 程序集成环境五、实验步骤1、了解语法制导翻译的方法，学习后缀式构造的语义动作；2、结合实验5的算符优先程序，设计程序构造后缀式；3、利用栈，编程实现后缀式的计算；4、测试程序运行效果：从文本文件中读表达式，在屏幕上输出，检查输出结果。

六、测试数据输入数据：编辑一个文本文文件expression.txt，在文件中输入如下内容：正确结果：（1）1+2;输出：1,2,+ 3（2）(1+2)*3;输出：1,2,+,3,* 9（3）(10+20)*30+(50+60*70)输出：10,20,+30,*50,60,70,*,+,+ 5150七、实验报告要求实验报告应包括以下几个部分：1、构造逆波兰式的语义动作；2、结合算符优先分析构造逆波兰式的算法和过程；3、语法制导翻译的运行方法；4、程序的测试结果和问题；5、实验总结。

中缀表达式变后缀表达式、后缀表达式（逆波兰）求值（python版本）定义：中缀表达式：在通常的表达式中，⼆元运算符总是置于与之相关的两个运算对象之间，这种表⽰法也称为中缀表达式后缀表达式：⼜叫逆波兰表达式，不包含括号，放在两个运算对象的后⾯，所有的计算按运算符出现的顺序，严格从左向右进⾏（不再考虑运算符的优先规则，如：(2 + 1) * 3 ，即2 1 + 3 *⼀个字符串表达式s = “9 + ( 3 - 1 ) * 3 + 10 / 2”）求值的过程分为两步(⼀) 将中缀表达式s变为后缀表达式s_after = "9 3 1 - 3 * + 10 2 / +",具体的规则如下：⾸先维护两个空栈，（stack_exp）存放逆波兰表达式，(stack_ops)暂存操作符，运算结束后stack_ops必为空循环遍历字符串(将表达式分为四种元素 1、数值; 2、操作符; 3、左括号; 4、右括号)，具体情况如下1、遇到数值，将该值⼊栈stack_exp2、遇到左括号，将左括号⼊栈stack_ops3、遇到右括号，将stack_ops中的操作符从栈顶依次出栈并⼊栈stack_exp，直到第⼀次遇到左括号终⽌操作（注意：该左括号出栈stack_ops但不⼊栈stack_exp）⾄此消除表达式中的⼀对括号4、遇到四则运算操作符号（+ - * /）4-1、如果stack_ops为空，操作符⼊栈stack_ops4-2、如果stack_ops不空，将stack_ops栈顶操作符与遍历到的操作符(op)⽐较：4-2-1：如果stack_ops栈顶操作符为左括或者op优先级⾼于栈顶操作符优先级， op⼊栈stack_ops，当前遍历结束4-2-2：如果op优先级⼩于或者等于stack_ops栈顶操作符， stack_ops栈顶操作符出栈并⼊栈stack_exp，重复4-1、 4-2直到op⼊栈stack_ops5、字符串遍历结束后如果stack_ops栈不为空，则依次将操作符出栈并⼊栈stack_exppython代码实现如下：ops_rule = {'+': 1,'-': 1,'*': 2,'/': 2}def middle_to_after(s):expression = []ops = []ss = s.split('')for item in ss:if item in ['+', '-', '*', '/']:while len(ops) >= 0:if len(ops) == 0:ops.append(item)breakop = ops.pop()if op == '('or ops_rule[item] > ops_rule[op]:ops.append(op)ops.append(item)breakelse:expression.append(op)elif item == '(':ops.append(item)elif item == ')':while len(ops) > 0:op = ops.pop()if op == '(':breakelse:expression.append(op)else:expression.append(item)while len(ops) > 0:expression.append(ops.pop())return expression(⼆) 将后缀表达式s_after = "9 3 1 - 3 * + 10 2 / +" 求值,具体的规则如下：初始化⼀个空栈stack_value，⽤于存放数值循环s_after1、如果遇到数字，⼊栈stack_value;2、如果遇到运算符，从stack_value中依次出栈两个数（先出栈的在右，后出栈的在左）连同遍历到的运算符组成⼆⽬运算，求值后将结果压栈stack_value3、继续遍历下⼀个元素，直到结束遍历完后stack_value中的结果便是表达式的值python代码实现如下：def expression_to_value(expression):stack_value = []for item in expression:if item in ['+', '-', '*', '/']:n2 = stack_value.pop()n1 = stack_value.pop()result = cal(n1, n2, item)stack_value.append(result)else:stack_value.append(int(item))return stack_value[0]def cal(n1, n2, op):if op == '+':return n1 + n2if op == '-':return n1 - n2if op == '*':return n1 * n2if op == '/':return n1 / n2if __name__ == '__main__':expression = middle_to_after('9 + ( 3 * ( 4 - 2 ) ) * 3 + 10 / 2')value = expression_to_value(expression)print value。

1.◆3.21③假设表达式由单字母变量和双⽬四则运算算符构成。

试写⼀个算法，将⼀个通常书写形式且书写正确的表达式转换为逆波兰式。

实现下列函数：char *RPExpression(char *e);/* 返回表达式e的逆波兰式 */Stack是⼀个已实现的栈。

可使⽤的相关类型和函数：typedef char SElemType; // 栈Stack的元素类型Status InitStack(Stack &s);Status Push(Stack &s, SElemType e);Status Pop(Stack &s, SElemType &e);Status StackEmpty(Stack s);SElemType Top(Stack s);------------------------------------------------------------------------------------------------- 拿到题⽬，要做的第⼀件事情，就是搞懂题⽬究竟要我们做什么，很显然，题⽬中的关键字是“逆波兰式”，那么⾸先我们要搞懂这个概念。

所谓的逆波兰表⽰法（Reverse Polish notation，RPN，或逆波兰记法），是⼀种数学表达式⽅式，在逆波兰记法中，所有操作符置于操作数的后⾯，因此也被称为后缀表⽰法。

逆波兰记法不需要括号来标识操作符的优先级。

（摘⾃维基） 举个简单的例⼦，平常我们写的数学表达式a+b，就是⼀种中缀表达式，写成后缀表达式就是ab+。

再举⼀个复杂的例⼦，中缀表达式(a+b)*c-(a+b)/e的逆波兰式是ab+c*ab+e/-。

在弄清楚概念以及题⽬的要求之后，接下来就要编写算法了。

那么将⼀个表达式转换为逆波兰式的算法思想是什么呢？ (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。