题解 | #表达式求值# 双栈

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        // 使用map记录各个操作的优先级
        Map<Character, Integer> priority = new HashMap<>();
        priority.put('*', 3);
        priority.put('+', 2);
        priority.put('-', 2);

        // 操作栈
        Stack<Character> operator = new Stack<>();

        // 数字栈
        Stack<Integer> numbers = new Stack<>();

        // 防止出现类似-2+4或者-()等类似情况
        numbers.push(0);
        int index = 0;
        while (index < s.length()) {
            char currrent = s.charAt(index);

            // 取出数字并入栈
            if (Character.isDigit(currrent)) {
                int j = index;
                while (j < s.length() && Character.isDigit(s.charAt(j))) {
                    j++;
                }
                int number = Integer.parseInt(s.substring(index, j));
                index = j;
                numbers.push(number);
                continue;
            }

            // 遇到后括号，一直计算到左括号，左括号出栈
            if (currrent == ')') {
                while (operator.peek() != '(') {
                    calculate(operator, numbers);
                }
                operator.pop();
            }

            // 遇到左括号则进栈
            if (currrent == '(') {
                operator.add('(');

                // 解决出现(-3+1)等符号开头的情况
                if (priority.containsKey(s.charAt(index + 1))) {
                    numbers.push(0);
                }
            }

            // 当前符号是操作符
            if (priority.containsKey(currrent)) {
                // 把操作符栈中优先级比当前操作符大的计算完
                while (!operator.isEmpty() && operator.peek() != '(' && priority.get(currrent) <= priority.get(operator.peek())) {
                    calculate(operator, numbers);
                }

                // 加入当前操作符
                operator.push(currrent);
            }
            index++;
        }

        // 计算剩下的操作
        while (!operator.isEmpty()) {
            calculate(operator, numbers);
        }
        return numbers.pop();
    }

    // pop出一个运算符和两个数，计算后结果push回数字栈
    private void calculate(Stack<Character> operator, Stack<Integer> numbers) {
        char operate = operator.pop();
        int num2 = numbers.pop();
        int num1 = numbers.pop();
        int ans = 0;
        if (operate == '+') {
            ans = num1 + num2;
        }
        if (operate == '-') {
            ans = num1 - num2;
        }
        if (operate == '*') {
            ans = num1 * num2;
        }
        numbers.push(ans);
    }
}