中缀表达式转换成后缀表达式

中缀表达式就是我们正常工作中写的表达式，如 a+(b-c)*d ，编译系统将中缀表达式改写 abc-d*+ ，这种运算符在操作数后面称为后缀表达式（也称逆波兰表达式）。

如何实现转换的呢？这里做一下自己的理解及记录。

利用栈来实现

转换过程需要用到栈，这里用两个栈，stack 栈用来存放运算符，post 栈用来存放最后的后缀表达式。具体规则如下：

从左到右扫描中缀表达式，若是操作数，直接存入 post 栈；

若是运算符：
（1）该运算符是左括号 ( , 则直接存入 stack 栈。
（2）该运算符是右括号 )，则将 stack 栈中 ( 前的所有运算符出栈，存入 post 栈。
（3）若该运算符为非括号，则将该运算符和 stack 栈顶运算符作比较：若高于栈顶运算符，则直接存入 stack 栈，否则将栈顶运算符出栈（从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止），存入 post 栈。
（4）当扫描完后，stack 栈中还有运算符时，则将所有运算符出栈，存入 post 栈。

例子：中缀表达式 a + b * c + (d * e + f) * g，其转换成后缀表达式则为a b c * + d e * f + g * +。

扫描	stack 栈	post 栈
a	空	a
a+	+	a
a+b	+	ab
a+b*	+*	ab
a+b*c	+*	abc
a+b*c+	+	abc*+
a+b*c+(	+(	abc*+
a+b*c+(d	+(	abc*+d
a+b*c+(d*	+(*	abc*+d
a+b*c+(d*e	+(*	abc*+de
a+b*c+(d*e+	+(+	abc*+de*
a+b*c+(d*e+f	+(+	abc*+de*f
a+b*c+(d*e+f)	+	abc*+de*f+
a+b*c+(d*e+f)*	+*	abc*+de*f+
a+b*c+(d*e+f)*g	+*	abc*+de*f+g
a+b*c+(d*e+f)*g#	空	abc*+de*f+g*+

注意：表格中第6步，读到+,因为栈顶元素*的优先级高，所以*出栈，栈中下一个元素+优先级与读到的操作符+一样，所以也要弹出。然后再将读到的+压入栈中。
第13步，读到)，则直接将栈中元素弹出直到遇到(为止。这里左括号前只有一个操作符+被弹出。

代码实现

import java.util.Stack;

public class InToPost {
    private Stack<Character> opStack;
    private Stack<Character> outStack;
    private String input;
    
    public InToPost(String in) {
        input = in;
        opStack = new Stack<Character>();
        outStack = new Stack<Character>();
    }
    
    public Stack<Character> doTrans() { //其他类型自行转换
        for (int i = 0; i < input.length(); i++) {
            char ch = input.charAt(i);
            switch (ch) {
            case '+':
            case '-':
                operationOpStack(ch, 1);
                break;
            case '*':
            case '/':
                operationOpStack(ch, 2);
                break;
            case '(':
                opStack.push(ch);
                break;
            case ')':
                operationParen();
                break;
            default:
                outStack.push(ch);
                break;
            }
        }
        while (!opStack.isEmpty()) {
            outStack.push(opStack.pop());
        }
        return outStack;
    }
    
    public void operationOpStack(char opThis, int prec1) {//运算符栈操作
        while (!opStack.isEmpty()) {
            char opTop = opStack.pop();
            if (opTop == '(') {
                opStack.push(opTop);
            }
            else {
                int prec2;
                if (opTop == '+' || opTop == '-')
                    prec2 = 1;
                else
                    prec2 = 2;
                if (prec2 < prec1) {
                    opStack.push(opTop);
                    break;
                }
                else
                    outStack.push(opTop);
            }
        }
        opStack.push(opThis);
    }
    public void operationParen() {
        while (!opStack.isEmpty()) {
            char c = opStack.pop();
            if (c == '(') 
                break;
            else
                outStack.push(c);
        }
    }
    
    public static void main(String[] args) {
        String input = "1+2*4/5-7+3/6";
        InToPost theTrans = new InToPost(input);
        Stack<Character> output = theTrans.doTrans(); 
        System.out.println("Postfix is " + output + '\n');
    }
}

利用语法树

先将中缀表达式用二叉树表示出来，再后序遍历该二叉树，就得到其相应的后缀表达式。

加括号法

加括号法先将中缀表达式每步要计算的表达式加上括号，然后将每个运算符移到其所在括号的外面，最后，从左到右去掉括号后就是后缀表达式。

例子： a+(b-c)*d

加括号 (a+((b-c)d))
移运算符 (a((bc)-d))+
去括号 abc-d*+

后缀表达式求值

求值过程可用栈来辅助存储。假定待求值的后缀表达式为：6 5 2 3 + 8 * + 3 + *，则其求值过程如下：

• 遍历表达式，遇到数字首先放入栈，此时栈如下 6 5 2 3

• 接着读到+，则弹出3和2，执行3+2，将结果5压栈 6 5 5

• 读到8，压栈 6 5 5 8

• 读到 *, 弹出8和5，执行8*5，将结果40压栈 6 5 40

• 读到 +,弹出40和5，执行40+5，将结果45压栈 6 45

• 读到 3,压栈 6 45 3

• 读到 +,弹出3和45，执行3+45，将结果48压栈 6 48

• 读到 *,弹出48和6，执行48*6，将结果288压栈 288

• 最后结果288