逆波兰表达式

问题背景

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

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

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

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

3、后缀表达式———将运算符放在两操作数的后面。后缀表达式也称逆波兰表达式，因其使表达式求值变得轻松，所以被普遍使用。 前缀和后缀表示法有三项公共特征：

（1） 操作数的顺序与等价的中缀表达式中操作数的顺序一致

数据结构试验报告

（2） 不需要括号

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

题目描述

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

一、需求分析

1、输入的形式和输入值得范围：输入一后缀表达式，相邻项之间以空格隔开，以#为结束标志，操作数为实数，操作符为 + - * / ； 2、输出的形式：如果表达式正确则输出表达式的计算结果，若不正确则输出错误提示

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

样例1： 输入： 2.5 3 * 5 - 3 + #（正确的输入）

输出：

************************ 运算结果是5.5

样例2： 输入： 2.5 3 * 3 - + #（错误的输入）

输出： 表达式错误!

************************

并弹出错误提示：

数据结构试验报告

二、概要设计

1、抽象数据类型：为实现以上功能，根据题目要求，采用链式栈来存储表达式的操作数，数据成员top用来指向链式栈第一个节点（栈顶），变量element用来存储栈顶节点的值，变量size用来记录当前栈的大小

链式栈的基本操作：

Lstack(int size = 0,sNode* top=NULL)；//栈的构造函数

void Insert(double a);//向栈中插入一元素 double pop();//取出栈顶元素

int GetSize(){ return size;}//返回当时栈的大小 计算表达式的函数：void Compute()； 2、算法的基本思想：

（1）成员Insert(double a )首先建立一新的节点并修改新产生的节点的next域指向栈顶，然后设置top指向新的链表节点，并把size的值加1

（2）成员pop()中如果栈的大小大于1，则返回栈顶元素，变量tos用来记录栈顶元素，p用来指向当前的栈顶节点，把top指向当前栈

数据结构试验报告

顶的下一个节点，然后释放p指向的节点，同时size减1，返回tos；如果栈的大小小于1，则抛出一整型异常

（3）函数Compute()中建立了链式栈s，并定义double 类型的变量x,y,字符类型的变量a。x存储操作数的整数部分，y保存小数部分

while()循环每次从键盘读入一个字符（用getchar()实现，空格也读进去）保存在a中，当a不是结束字符（#）时，运用switch(a)语句，当a 是操作符的时候从栈中取出两个元素（pop()）进行相应的运算，并将运算结果插入栈中，【try…catch….语句捕捉出栈时返回的错误信息】当a 是数字的时候把从此开始的浮点数字符串转化为一个浮点数，并把此浮点数插入到栈中

当扫描完毕后如果栈中的元素多于一个则表达式错误，输出错误信息；否则输出栈顶元素，此时栈顶元素即为表达式的值 3、主程序的流程：该主程序中只有函数Compute()的调用

三、详细设计

1、物理数据类型：表达式的操作数应为实数范围因此定义为double类型，计算结果也为实数因此也为double类型。从键盘读入的元素都放在字符变量a 中，链式栈的节点sNode定义如下 struct sNode{ };

2、算法的时空分析和改进设想：由于从键盘读入的数据都保存在char double element;//操作数

sNode* next;//指向下一个节点的指针

数据结构试验报告

类型的变量a 中，所以当a是操作符的时候没什么问题，但当a是数字的时候时需要将a 转换成double类型的，当操作数很复杂的时候，例如156.234时，需要分别计算出其整数部分和小数部分然后再相加，此时算法的时间消耗就比较大。可以计算得到在输入的表达式正确的前提下，最理想的情况下（操作数都是小于10的整数）算法的时间复杂度是O(n),n表示操作数的个数。

算法的改进设想：本算法的主要时间消耗在于操作数的读取上（在操作数比较复杂的时候），因此如果能省去这个时间，则算法的效率就会提高。我们可以用double类型的变量x来保存从键盘读取的元素，如果读到的x是操作符的话，操作符+ - * / 都有其对应的ASCII码值，+（43） -（45） *（42） /（47）可以同过其ASCII码值来判断进行什么操作，如果是操作数的话则直接放入栈中，省去了while()循环来读取操作数，但这样操作数中出现42，43,45,47是就会出现错误。另外可以将两个操作数计算得到的结果保存到当时的栈顶中从而可以省掉一些节点的申请和释放。 3、函数之间的调用关系：

Lstack s 建立栈 s.Insert() 往栈中插入元素 Compute

s.pop()取出栈顶元素 s.pGetSize()返回栈的大小

数据结构试验报告

4、输入输出格式：输入为一要计算的表达式的后缀形式，相邻项之间以空格隔开，并以 # 作为结束标志；输出格式：若输入的表达式正确则输出表达式的计算结果（输出到屏幕上），若表达式错误，则输出错误提示，具体格式如下：

输入： 2.5 3 * 5 - 3 + #（正确的输入后缀表达式） 输出：

************************ 运算结果是5.5

四、调试分析

调试过程中主要出现了以下问题：对输入的正确表达式程序得不

到正确的结果，原因是在switch()语句中出现了问题，在case语句执行完以后忘了加break;使得其逻辑出现问题；另外，对于错误的输入程序不能及时的输出错误提示，后来通过是用try…catch…语句解决了这个问题。

五、测试结果：

样例1： 输入 15 3 * 0.2 + 40 - #（正确的输入后缀表达式）

输出 ************************

运算结果是5.2

Press any key to continue

样例2： 输入 1.5 2.5 * 6 + - #（输入错误的后缀表达式） 输出 表达式错误!

************************

弹出错误提示：

数据结构试验报告

六、使用说明

1、本程序的执行环境为visualc++

2、运行程序时 输入为表达式的后缀形式，操作符限于 + - * / ，操作数在实数范围之内。输入以 # 作为结束标志；如果输入正确则输出表达式相应的值，如果错误则输出错误提示

七、实验心得 八、附件

Compute1.txt 主程序（从键盘读写并输出到屏幕上）

Compute2.txt 程序说明：本程序从文件question.txt中读取后缀表达式，并将计算结果保存到answer.txt中（表达式正确），表达式错误时输出错误提示，操作数是实数。