2.4 后序表达式

■ 402006 后序表达式

【题目描述】后序表达式（ReversePolish）

编程求一个表达式的运算结果。用户输入一个包含“＋”“−”“*”“/”，以及正整数、圆括号的合法数学表达式，程序可以输出该表达式的运算结果。

【输入格式】

输入一个合法的数学表达式，不超过100个字符，保证有正确的结果。

【输出格式】

输出该表达式的运算结果，保留两位小数（无须四舍五入）。

【输入样例】

(30−2*5)−3*8/4

【输出样例】

14.00

【算法分析】

表达式是由操作数、运算符及分隔符组成的，一般我们使用的是中序表示法，也就是将运算符写在两个操作数之间，例如：

X＋Y

X＋Y*Z

由于表达式的运算符有优先级，故要用计算机直接运算用户输入的诸如(5−4)/(6*2)−8＋2 这样的中序表达式是很不方便的。通常的解决方法是用字符串形式接收表达式并根据运算优先级将之转换为前序表达式或后序表达式（又称逆波兰式）。

前序表达式是将运算符写在两个操作数之前的表达式，例如：＋XY、＋X*YZ。

后序表达式是将运算符写在两个操作数之后的表达式，例如：XY＋、XYZ*＋。

中序表达式转换为后序表达式的方法如下。

定义一个字符串保存后序表达式，再定义一个堆栈保存运算符，对表达式中的字符ch从左到右依次扫描。

（1）若ch为数字，将后续的所有数字依次存入后序表达式字符串。

（2）若ch为左括号，将此括号入栈。

（3）若ch为右括号，使堆栈中左括号以前的字符依次出栈并将其存入后序表达式字符串，然后将左括号删除。

（4）若ch为“＋”“−”“*”“/”，要先使所有优先级高于或者等于运算符的栈顶元素依次出栈并将其存入后序表达式字符串后（越早存入后序表达式字符串的运算符，越早进行运算），再将ch入栈。例如，当ch为“＋”或“−”时，使当前堆栈中左括号以前的所有字符依次出栈并将其存入后序表达式字符串，然后将ch入栈（因为其优先级低）；当ch为“*”或“/”时，使当前栈中的栈顶连续的“*”和“/”出栈并依次将其存入后序表达式字符串，然后将ch入栈。

（5）表达式扫描完后，依次输出堆栈中的运算符到后序表达式字符串。

例如，将A/B−C*(D＋E)转换成后序表达式的过程如表2.1所示。

运算后序表达式的方法是对后序表达式从左到右依次扫描，遇到数字就将其存入堆栈中，遇到运算符就执行两次删除堆栈中元素的操作并进行运算，将结果入栈。如此重复执行直至表达式为空即可。

例如，有一个后序表达式AB/CDE＋*−，其操作过程如下。

（1）堆栈中存入AB，在读到“/”时，取出A和B，进行除法运算后将结果X入栈。

（2）堆栈中存入CDE，遇到“＋”，取出DE相加后将结果Y入栈。

（3）遇到“*”，取出Y，与C相乘后将结果入栈。

（4）遇到“−”，取出堆栈中仅剩的两个数进行相减得出结果。

参考程序如下。

类似地，运算前序表达式的方法是从右至左扫描表达式，遇到数字则入栈，遇到运算符则出栈两次获得操作数，其中第一次出栈的数作为被操作数，第二次出栈的数作为操作数。运算子表达式，然后使结果入栈……

例如中序表达式2*3/(2−1)+3*(4−1)的前序表达式是+/*2 3−2 1*3−4 1，请手动模拟其运算过程。 oUtZJMR+tw3Ev2N3lfI5/bS02XDguiK652/GWqWQsMczAb+jz5TOiZuMgVmsTcyK