简介

逆波兰式也叫后缀表达式(运算符写在操作数之后)

定义

一个表达式E的后缀形式可以如下定义：

1. 如果E是一个变量或者常量，E的后缀式是E本身
2. 如果E是E1 op E2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1'E2'op，这里E1'和E2'分别为E1和E2的后缀式
3. 如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀式

举个例子

a+b(中缀表达式) ====> ab+(后缀表达式)

(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/-

为什么要搞一个逆波兰式

因为计算机不好理解中缀表达式，逆波兰式在计算机看来是比较简单易懂的结构，因为计算机普遍采用的内存结构是栈式结构，执行先进后出的顺序。

计算方法

新建一个表达式，如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作为相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。

特点

逆波兰表达式的长度为n，n是奇数时，其中包含的数字最多有(n+1)/2个 包含的字符最多有(n-1)/2个，当n为偶数时，不能构成合法的逆波兰表达式。