逆波兰表示

数据结构

20世纪50年代，波兰逻辑学家提出了一种不需要括号的后缀表示法，也成为逆波兰(Reverse Polish Notatiojn ,RPN)表示。

后缀表达式：所有的符号都要在要运算的数字的后面出现。例如：“9+(3-1)x3+10/2”后缀表达式为：“9 3 1 - 3 * + 10 2 / +”

后缀表达式计算结果

对于“9 3 1 - 3 * + 10 2 / +”为例：

1. 初始化空栈
2. 9、3、1进栈，栈为9-3-1
3. 对于“-”，1出栈作为减数，3出栈作为被减数，结果得到2再次进栈，栈为9-2
4. 3 进栈，栈2为9-3-2
5. 对于“*”，3出栈，2出栈，得到6，结果入栈，栈为9-6
6. 对于“+”，6出栈，9出栈，得到15，结果入栈，栈为15
7. 10和2进栈，栈为15-10-2
8. 对于“\”，2出栈，10出栈，得到5，结果入栈，栈为15-5
9. 对于“+”，5出栈，15出栈，得到20，结果入栈，栈为20
10. 20出栈，栈为空。

import java.util.Stack;
public class RPN {
    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<Integer>();
        for(int i = 0;i<tokens.length;i++){
            try{
                int num = Integer.parseInt(tokens[i]);
                stack.add(num);
            }catch (Exception e) {
                int b = stack.pop();
                int a = stack.pop();
                stack.add(get(a, b, tokens[i]));
            }
        }
        return stack.pop();
    }
    private static int get(int a,int b,String operator){
        switch (operator) {
        case "+":
            return a+b;
        case "-":
            return a-b;
        case "*":
            return a*b;
        case "/":
            return a/b;
        default:
            return 0;
        }
    }
    public static void main(String[] args) {
        String[] strlist = {"2", "1", "+", "3", "*"};
        System.out.println(evalRPN(strlist));
    }
}