逆波兰式(Reverse Polish notation，RPN，或逆波兰记法)，也叫后缀表达式(将运算符写在操作数之后)

• 中文名称 逆波兰式
• 外文名称 Reverse Polish notation，RPN
• 又称 后缀表达式
• 使用方式 将运算符写在操作数之后

算法定义

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

　　(1)如果E是一个变量或常量，则E的后缀式是E本身。

360百科　　(2)如果E是E1 op E2形式的表达式，这里op是任何振二元操作符，则E的后缀式为E零观官1'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)-

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

　　→(ab+c*)(ab+e/)酒厂独八束-

　　→ab+c*ab+e久笑端充究/-

算法作用

　　实现逆波兰式的算法，难度并不扬例油掉笔育某同树乐大，但为什么要将看似简单的中缀表达式转换为复杂的逆波兰式?原因就在于这个简单是相对人类的思维结构黑吗来说的，对计算机而言中序表达式是非常复杂的结象足蛋请菜巴节蛋构。相对的，逆波兰式在计算机轮红华审升看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。

算书这抓空步希盐布赵审生法实现

　　将一个普通的中缀表达式转换为逆波兰表达式的一般算法是:

　　首先需要分配2个栈，一个作为临时存储运算符的栈S1(含一个结束符号)，一个作为存放山范练似耐严协低谈结果(逆波兰式)的栈S2(空栈)，S1栈可先放入优先级最低的运算符#，注意，中缀式应以此最低优先级的运算符字掉台结束。可指定其他字符，不一定非#不可。从中缀式的左端开始取字符，逐序进行如下步骤:

　　(1)若取出的字符是操作数，则分来自析出完整的运算数，360百科该操作数直接送入S2栈。

　　(2)若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较，如果该运算符(不包括括号运算符)优先级高于S1栈栈顶运算符(包括左括号)优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符(包括左括号)低于(不包括等于)该运算符优先级时停止弹出运算符，最后将该运算符送入S1栈。

　　(3)若取出的也游只金叶阻慢动久脚字符是"("，则直接送入S1栈顶。

　　(4)若取出的字符是")"，则将距离S1栈栈顶最近的"("之间的运算符，逐个出栈，依次送入S2栈，此时抛弃"("。

　　(5)重复上面的1~4步，直至处理完所有的输入字符。

　　(6)若取出的字符是"#"，则将S1栈内所有运算符(不包括"#")，逐个出栈，依次送入S2栈。

　　完成以上据阿步骤，S2栈便为未马愿乐温逆波兰式输出结果。不过万福触命交投她S2应做一下逆序处理。便可以按房或易阳王选侵整呼落到照逆波兰式的计算方法计算了!

计算方法

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

算法举例

　　下面以(a+b)*c为例子进鲁案行说明:

　　(a+b)*c的逆波兰式为ab+c*，假设计算机把ab+c*按从左到右的顺序压入栈中，并且按照遇到运算符就把栈顶两个元素出栈，执行运算，得到的结果再入栈的早厂额省善案按节逐须快原则来进行处理，那么ab+c*的执行结果如下:

　　1)a入栈(0位置)

　　2)b入栈(教水感1位置)

　　3)遇到运算符"+"，将a和b出栈，执行a+b的操作，得到结果d=a+b，再将d入栈(0位置)

　　4)c入栈(现意方话革赵影都兴可1位置)

　　5)遇到运算符"*"，将d和c出栈，执行d*c的操作，得到结果e，再将e入栈(0位置)

　　经过以上运算，计算机就可以得到(a+b)*c的运算结果e了。

　　逆波兰式除了可以实现上述类型的运算，它还可以派生出许多新的算法，术酸久死客呀氢序作数据结构，这就需要灵活运用了。逆波兰式只是一种序列矿支前由推影想留落这序体现形式。

算法图示

　　其中△非异责水代表一个标识，ω代表预算法，名字Q代表变量(如int a，b等)，

　　算法用到三个栈:a栈，b栈，i包互蛋n栈。

　　其中a栈用来存储逆波兰式，b用来存储△号和运算符，in栈为输入栈。

　　第一竖排为b栈中符号，第一横排为输入栈中符号。

　　pop(in)为输入栈栈顶元素出栈，pop(a，Q)为Q入a栈，NEXT算法即为进行下一轮循环，其中ω1

　　算法开始时，现将△如b栈，输入栈以#号结尾。

　　?

程序实现

　　C/C++语言版

　　数据结构版

　　还有一种方法,用2叉树.

二叉树法

　　将最终进行的运算符记为根节点，将两边的表达式分别记为左右子树，依次进行直到所有的运算符与数字或字母标在一棵二叉树上。然后对二叉树进行后序遍历即可。