题解 | 表达式求值

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待 计算的表达式
     * @return int整型
     */
    public static int solve(String s) {
        Stack<Integer> nums = new Stack<>();
        Stack<Character> ops = new Stack<>();

        int n = s.length();
        int i = 0;
        while (i < n) {
            char c = s.charAt(i);

            if (c == ' ') {
                i++;
                continue;
            }

            if (Character.isDigit(c)) {
                //多位数字
                int num = 0;
                while (i < n && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + (s.charAt(i) - '0');
                    i++;
                }
                nums.push(num);
                continue;
            }

            if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                while (ops.peek() != '(') {
                    compute(nums, ops);
                }
                ops.pop(); // 弹出左括号
            } else if (isOperator(c)) {
                //表达式是从做往右计算的 在中间遇到运算符号时根据优先级  如果左边的符号优先级大于等于右边符号的优先级左边的即可先运算了
                // 运算符优先级判断
                while (!ops.isEmpty() && precedence(ops.peek()) >= precedence(c)) {
                    compute(nums, ops);
                }
                ops.push(c);
            }
            i++;
        }

        while (!ops.isEmpty()) {
            compute(nums, ops);
        }

        return nums.pop();
    }

    private static void compute(Stack<Integer> nums, Stack<Character> ops) {
        int b = nums.pop();
        int a = nums.pop();
        char op = ops.pop();
        if (op == '+') nums.push(a + b);
        else if (op == '-') nums.push(a - b);
        else if (op == '*') nums.push(a * b);
    }

    private static boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*';
    }

    private static int precedence(char op) {
        if (op == '+' || op == '-') return 1;
        if (op == '*') return 2;
        return 0;
    }
}