题解 | 表达式求值

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    static public int solve(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        s = s.replaceAll("\\s+", "");
        Stack<Integer> nums = new Stack<>();
        Stack<Character> ops = new Stack<>();
        int n = s.length();

        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);

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

            if (Character.isDigit(c)) {
                // 处理数字
                int num = 0;
                while (i < n && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + (s.charAt(i) - '0');
                    i++;
                }
                i--;
                nums.push(num);
            } else if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                while (!ops.isEmpty() && ops.peek() != '(') {
                    nums.push(applyOp(ops.pop(), nums.pop(), nums.pop()));
                }
                ops.pop(); // 弹出 '('
            } else if (c == '+' || c == '-' || c == '*' || c == '/') {
                // 处理负号的情况
                if (c == '-' && (i == 0 || s.charAt(i - 1) == '(' ||
                                 isOperator(s.charAt(i - 1)))) {
                    // 这是一个负数，不是减号
                    i++;
                    int num = 0;
                    while (i < n && Character.isDigit(s.charAt(i))) {
                        num = num * 10 + (s.charAt(i) - '0');
                        i++;
                    }
                    i--;
                    nums.push(-num);
                } else {
                    // 处理运算符优先级
                    while (!ops.isEmpty() && precedence(c) <= precedence(ops.peek())) {
                        nums.push(applyOp(ops.pop(), nums.pop(), nums.pop()));
                    }
                    ops.push(c);
                }
            } else {
                throw new IllegalArgumentException("非法字符: " + c);
            }
        }

        // 计算剩余的表达式
        while (!ops.isEmpty()) {
            nums.push(applyOp(ops.pop(), nums.pop(), nums.pop()));
        }

        if (nums.size() != 1) {
            throw new IllegalArgumentException("表达式格式错误");
        }

        return nums.pop();
    }

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

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

    private static int applyOp(char op, int b, int a) {
        switch (op) {
            case '+':
                return a + b;
            case '-':
                return a - b;
            case '*':
                return a * b;
            case '/':
                if (b == 0) {
                    throw new ArithmeticException("除零错误");
                }
                return a / b;
            default:
                throw new IllegalArgumentException("未知运算符: " + op);
        }
    }
}