题解 | #表达式求值#

两个栈 st1 和 st2，一个用来存操作数 （st1) ，一个用来存运算符和左括号 (st2)。

1. 当遇到 '(' 就入 st2 栈。
2. 当遇到操作数就如 st1 栈。
3. 当遇到操作符，有两种情况
   3.1 如果这个操作符优先级小于等于 st2 栈顶操作符的优先级，则从 st1 中出栈两个操作数，从 st2 中出栈一个操作符，并做运算，将运算结果放入 st1 栈中。
   3.2 如果这个操作符优先级大于 st2 栈顶操作符的优先级，则直接入栈。
4. 当遇到 ')' ，每次出栈两个操作数和一个操作符，并将运算结果存入 st1 中，直到 st2 栈顶为 '(' ，并将这个 '(' 出栈。

public class Solution {
    
    public int solve (String s) {
        // write code here
        Map<Character, Integer> priority = new HashMap<>();
        priority.put('+', 1);
        priority.put('-', 1);
        priority.put('*', 2);
        Deque<Integer> stack1 = new LinkedList<>(); // 存放操作数
        Deque<Character> stack2 = new LinkedList<>(); // 存放运算符和左括号
        s = "(" + s + ")"; // 这样可以使结束后栈中仅剩的一个数就是结果
        int i = 0;
        while(i < s.length()){
            char ch = s.charAt(i);
            if(ch == '('){
                stack2.push(ch);
            }else if(ch - '0' >= 0 && ch - '0' <= 9){
                int num = 0;
                // 累加操作数
                while(Character.isDigit(s.charAt(i))){
                    num = num * 10 + s.charAt(i) - '0';
                    i++;
                }
                i--;
                stack1.push(num);
            }else if(ch == '+' || ch == '-' || ch == '*'){
                if(!stack2.isEmpty() && priority.containsKey(stack2.peek()) && priority.get(ch) <= priority.get(stack2.peek())){
                    int b = stack1.pop();
                    int a = stack1.pop();
                    char op = stack2.pop();
                    int c = operation(a, op, b);
                    stack1.push(c);
                }
                stack2.push(ch);
            }else{
                while(!stack2.isEmpty() && stack2.peek() != '('){
                    int b = stack1.pop();
                    int a = stack1.pop();
                    char op = stack2.pop();
                    int c = operation(a, op, b);
                    stack1.push(c);
                }
                stack2.pop();
            }
            i++;
        }
        return stack1.pop();
    }
    
    private int operation(int a, char op, int b){
        if(op == '+') return a + b;
        if(op == '-') return a - b;
        if(op == '*') return a * b;
        return a / b;
    }
}