一、什么是逆波兰表达式

逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后），指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。

后缀表达式计算：

后缀表达式计算与前缀表达式类似，只是顺序是从左至右，具体过程如下：

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

例如：后缀表达式为“2 3 + 4 × 5 -”计算过程如下：

  （1）从左至右扫描，将 2 和 3 压入堆栈；

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

  （3）将 4 入栈；

  （4）接下来是 × 运算符，因此弹出 4 和 5，计算出 4 × 5 = 20，将 20 入栈；

  （5）将 5 入栈；

  （6）最后是-运算符，计算出 20-5 的值，即 15，由此得出最终结果。

中缀表达式转后缀表达式：

与转换为前缀表达式相似，步骤如下：

  （1）初始化两个栈：运算符栈s1和储存中间结果的栈s2；

  （2）从左至右扫描中缀表达式；

  （3）遇到操作数时，将其压s2；

  （4）遇到运算符时，比较其与 s1 栈顶运算符的优先级：

    a：如果 s1 为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；

    b：否则，若优先级比栈顶运算符的高，也将运算符压入 s1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）;

    c：否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到（4）-（1）与s1中新的栈顶运算符相比较；

  （5）遇到括号时：

    a：如果是左括号“(”，则直接压入 s1；

    b：如果是右括号“)”，则依次弹出 s1 栈顶的运算符，并压入 s2 ，直到遇到左括号为止，此时将这一对括号丢弃；

  （6）重复步骤（2）至（5），直到表达式的最右边；

  （7）将 s1 中剩余的运算符依次弹出并压入 s2；

  （8）依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）

例如，将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下：

(a+b)*c-(a+b)/e

→((a+b)*c)((a+b)/e)-

→((a+b)c*)((a+b)e/)-

→(ab+c*)(ab+e/)-

→ab+c*ab+e/-

得到的最终结果为：“ 1 2 3 + 4 × + 5 – ”

逆波兰式的作用

实现逆波兰式的算法，难度并不大，但为什么要将看似简单的中缀表达式转换为复杂的逆波兰式？原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。

延伸阅读：

二、什么是波兰表达式

我们日常的运算表达式通常是如下形式，这种成为中缀表达式，也就是运算符在运算数的中间。这种表达式人类很容易识别，并根据其进行计算，但计算机识别这种表达式非常困难。

a + b * (c – d) + e/f

因此，1920年，波兰科学家扬·武卡谢维奇（Jan ukasiewicz）发明了一种不需要括号的计算表达式的表示法将操作符号写在操作数之前，也就是前缀表达式，即波兰式（Polish Notation, PN）。上述中缀表达式转换为波兰表达式的格式如下：

+a+*b–cd/ef

从上面表达式可以看出，运算符在2个运算数的前面，因此波兰表达式也称为前缀表达式。为了便于理解，我们给出一个具体的实例，这个实例将上面的字母换成具体的数字（1 + 2 * (4 – 3) + 6/2），这个结果很容易看出来，也就是1 + 2*1 + 3 = 6。然后我们看一下波兰表达式的表示形式及运算过程。

+1+*2-4 3/ 6 2 // 从右向左扫描，当遇到运算符时计算其最近的右侧2个运算数

+1+*2-4 3 3   //先计算最右侧的数据，也就是 6/2=3

+1+*2 1 3     // 同理，4-3 = 1

+1+2 3         // 同理， 2*1= 1

+1+5 

6

通过上面示例可以大概理解波兰表达式的计算过程。

上一篇

制作项目排期表用什么软件好?

下一篇

多路归并排序的时候，为什么要采用败者树?