1 什么是逆波兰表达式？

以表达式 1 - 2 * ( 3 - 4 ) 为例，有如下三种写法；

1. 1 - 2 * ( 3 - 4 ): 中缀表达式，大家容易理解的新式，运算符在中间；
2. - 1 * 2 - 3 4: 前缀表达式，运算符在前面，也称为波兰表达式；
3. 1 2 3 4 - * -: 后缀表达式，运算符在后面，也称为逆波兰表达式；

逆波兰表达式，Reverse Polish notation，为了纪念波兰科学家；

我在1924年突然有了一个无需括号的表达方法，我在文章第一次使用了这种表示法。

2 逆波兰表达式生成规则

1. 从左至右扫描中缀表达式；
2. 操作数：将其放入操作数栈中；
3. 左括号：直接放入运算符栈；
4. 右括号：弹出运算符栈顶元素至操作数栈中，直到遇到左括号为止；
5. 运算符：与运算符栈栈顶元素比较优先级，不大于则弹出运算符栈栈顶元素至操作数栈中，直到大于栈顶元素优先级；
6. 扫描完表达式后，如果运算符栈不为空，依次弹出至操作数栈中；

3 简易计算器

给定一个字符串，实现一个计算器并返回结果。

class Solution {

    public int calculate(String s) {
        Deque<Integer> numStack = new LinkedList<>();
        Deque<Character> opStack = new LinkedList<>();
        int len = s.length();
        // 上一个有效的字符
        Character last = null;
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c == ' ') continue;
            if (c == '(') {
                opStack.addLast(c);
            } else if (c == ')') {
                calculate(numStack, opStack, 0);
                opStack.removeLast();
            } else if (Character.isDigit(c)) {
                int n = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    n = n * 10 + (s.charAt(i) - '0');
                    i++;
                }
                i--;
                numStack.addLast(n);
            } else {
                // 负数补0
                if (c == '-' && (last == null || last == '(')) {
                    numStack.addLast(0);
                }
                calculate(numStack, opStack, getPriority(c));
                opStack.addLast(c);
            }
            last = c;
        }
        // 处理完剩余的运算符
        calculate(numStack, opStack, 0);
        return numStack.removeLast();
    }

    /**
     * 如果栈顶运算符优先级不大于priority，则进行递归处理
     */
    private void calculate(Deque<Integer> numStack, Deque<Character> opStack, int priority) {
        if (opStack.isEmpty()) return;
        if (opStack.getLast() == '(' || priority > getPriority(opStack.getLast())) return;
        Character op = opStack.removeLast();
        // 注意操作数顺序
        Integer right = numStack.removeLast(), left = numStack.removeLast();
        int res;
        if (op == '+') res = left + right;
        else if (op == '-') res = left - right;
        else if (op == '*') res = left * right;
        else if (op == '/') res = left / right;
        else return;
        numStack.addLast(res);
        calculate(numStack, opStack, priority);
    }

    /**
     * 返回运算符优先级，注意左括号最低
     */
    private int getPriority(char c) {
        if (c == '(') return -1;
        else if (c == '+' || c == '-') return 1;
        else return 2;
    }
}