表达式avb cvd逆波兰表达式

数据结构试验报告

问题背景

表达式求值是程序设计语言编译中的一个最基本的问题．因为任何程序设计语言都必须具有表达式求值的功能，同时表达式的计算应用也相当广泛，比如电力调度系统中的计算遥测、车站票务系统中的票价类型计算公式等。

通常，我们所说的表达式是由运算符、操作数、界限符所组成。而算术表达式中最常见的表示法形式有中缀、前缀和后缀表示法。中缀表示法是书写表达式的常见方式，而前缀和后缀表示法主要用于计算机科学领域。

1、中缀表达式———将运算符放在两操作数的中间。在运算中存在运算符的优先权与结合性的问题。例如运算：a*b+(c-d/e)*f 时，编译器即自左向右逐一检查，当检查到第一个运算符“*”时还无法知道是否执行；待检查到第二个运算符“ + ”时，因为知道“*”的优先级别高于“ + ”时，才知道执行“a*b”；当继续检查到“ ( ”时，可知道先执行括号以内部分等。

2、前缀表达式———将运算符放在两操作数的前面。这种表示法经常用于计算机科学，特别是编译器设计方面。为纪念其发明家—Jan

Lukasiewicz，这种表示法也称波兰表示法。

3、后缀表达式———将运算符放在两操作数的后面。后缀表达式也称逆波兰表达式，因其使表达式求值变得轻松，所以被普遍使用。

前缀和后缀表示法有三项公共特征：

（1） 操作数的顺序与等价的中缀表达式中操作数的顺序一致 数据结构试验报告

（2） 不需要括号

（3） 操作符的优先级不相关

题目描述

读入一个后缀表达式，利用堆栈来计算该表达式的值，同时要效验后缀表达式是否正确，并输出相关信息

一、需求分析

1、输入的形式和输入值得范围：输入一后缀表达式，相邻项之间以空格隔开，以#为结束标志，操作数为实数，操作符为 + - * / ；

2、输出的形式：如果表达式正确则输出表达式的计算结果，若不正确则输出错误提示

3、程序的功能：从键盘读入一后缀表达式（操作数是实数），如果表达式正确输出表达式的计算结果，如果表达式错误，则输出错误提示。

逆波兰表达式、波兰表达式【数据结构与算法】

逆波兰表达式、波兰表达式【数据结构与算法】

1.前缀表达式⼜称波兰式，前缀表达式的运算符位于操作数之前。⽐如:- × + 3 4 5 6

2.中缀表达式就是常见的运算表达式，如(3+4)×5-6

3.后缀表达式⼜称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后,⽐如:3 4 + 5 × 6 -

⼈类最熟悉的⼀种表达式1+2，(1+2)3，3+42+4等都是中缀表⽰法。对于⼈们来说，也是最直观的⼀种求值⽅式，先算括号⾥的，然后算乘

除，最后算加减，但是，计算机处理中缀表达式却并不⽅便。

然后我们还需明确⼀些概念，下⾯通过我们最熟悉的中缀表达式画出⼀棵语法树来直观认识⼀下前后缀表达式的⽣成。以A+B*(C-D)-E*F为

例：

中缀表达式得名于它是由相应的语法树的中序遍历的结果得到的。上⾯的⼆叉树中序遍历的结果就是A+B*(C-D)-E*F。

前缀表达式是由相应的语法树的前序遍历的结果得到的。上图的前缀表达式为- + A * B - C D * E F

后缀表达式⼜叫做逆波兰式。它是由相应的语法树的后序遍历的结果得到的。上图的后缀表达式为：A B C D - * + E F * -

下⾯我们关注两个点：

1.如何根据⼀个逆波兰表达式求出运算结果？

2.如果将⼀个中缀表达式转换成后缀表达式（逆波兰表达式）

⼀.通过逆波兰表达式计算结果

我们先看⼀个例⼦...后缀表达式3 4 + 5 × 6 -的计算

1.从左⾄右扫描，将3和4压⼊堆栈；

2.遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素，注意与前缀表达式做⽐较），计算出3+4的值，得7，再将7⼊栈；

3.将5⼊栈；

4.接下来是×运算符，因此弹出5和7，计算出7×5=35，将35⼊栈；

5.将6⼊栈；

6.最后是-运算符，计算出35-6的值，即29，由此得出最终结果。

从上⾯的过程我们如何编写代码实现呢？

可以采⽤⼀个辅助的栈来实现计算，扫描表达式从左往右进⾏，如果扫描到数值，则压进辅助栈中，如果扫描到运算符，则从辅助栈中弹出

把表达式转换为逆波兰表达式的方法

把表达式转换为逆波兰表达式的方法

什么是逆波兰表达式？

逆波兰表达式（Reverse Polish Notation，简称RPN）是一种数学表达式的表示方法，其中运算符位于操作数的后面，而不是中间。例如，将中缀表达式 3 + 4 转换为逆波兰表达式的结果是 3 4 +。

为什么要使用逆波兰表达式？

逆波兰表达式具有以下优点：

1. 不需要括号：逆波兰表达式由于运算符在操作数的后面，所以不需要括号来定义运算次序。

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

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

方法一：使用栈实现转换

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

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

3. 如果遇到操作数（数字），则直接添加到逆波兰表达式列表中。 4. 如果遇到运算符，按照以下规则处理：

– 如果栈为空或栈顶为左括号（或无运算符优先级低于当前运算符），则直接将运算符入栈。

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

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

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

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

方法二：使用递归实现转换

1. 定义一个递归函数，传入表达式和当前处理位置。

2. 判断当前位置处的字符：

– 如果是数字，则直接返回该数字。

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

– 如果是左括号，则继续向后处理直到找到对应的右括号。 3. 递归函数返回结果即为转换后的逆波兰表达式。

江苏科技大学 计算机学院 编译原理实验报告0941901228 章进兴

实验三 逆波兰表达式的产生及计算

一、实验目的

非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。

二、实验内容

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

三、逆波兰表达式的产生及计算实验设计思想及算法

 逆波兰式定义

将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。

 产生逆波兰式的前提

中缀算术表达式

 逆波兰式生成的设计思想及算法

(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。

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

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

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

做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。

(5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 江苏科技大学 计算机学院 编译原理实验报告0941901228 章进兴

运用以上算法分析表达式(a+b*c)*d的过程如下：

当前符号 输入区 符号栈 输出区

（ a+b*c)*d

a +b*c)*d (

+ *c)*d ( a