题解 | 表达式求值

import java.util.*;

public class Main {

// 符号计算的优先级：值越大，优先级越高
    static Map<String, Integer> symbolPriority = new HashMap<>(4);
    static {
        symbolPriority.put("+", 1);
        symbolPriority.put("-", 1);
        symbolPriority.put("*", 2);
        symbolPriority.put("/", 2);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String a = in.next();
        // String a = "-1*(-1-1)";

        List<String> list = parseList(a);
        List<String> orderList = orderList(list);
        int sum = computeList(orderList);

        System.out.println(sum);
    }

// 计算
    public static int computeList(List<String> list) {
        Stack<Integer> sumSta = new Stack<>();
        int res;
        int num1 = 0, num2 = 0;
        for (String s : list) {
            if (s.matches("\\d+") || s.matches("-\\d+")) {    // 如果是数（支持负数），就压栈
                sumSta.push(Integer.parseInt(s));
            } else {
                num1 = sumSta.pop();
                num2 = sumSta.pop();
                switch (s) {
                    case "+":
                        res = num2 + num1;
                        break;
                    case "-":
                        res = num2 - num1;
                        break;
                    case "*":
                        res = num2 * num1;
                        break;
                    case "/":
                        res = num2 / num1;
                        break;
                    default:
                        throw new RuntimeException("扫描到未知符号！");
                }
                sumSta.push(res);
            }
        }
        return sumSta.pop();
    }

// 将中缀表达式转换为后缀表达式:
    public static List<String> orderList(List<String> list) {
        // 数字+ 优先级排序后的符号
        List<String> orderList = new ArrayList<>();
        // 临时的低优先级符号存储
        Stack<String> tempChar = new Stack<>();

        for (String s : list) {
            if (s.matches("\\d+") || s.matches("-\\d+")) { // （支持负数）
                orderList.add(s);
                continue;
            }

            switch (s) {
                case "(":
                    tempChar.push(s);
                    break;

                case ")":
                    // 弹出 chat 中的符号，添加到 num 中，直至遇到 (
                    while (!"(".equals(tempChar.peek())) {  // peek() 查看栈顶元素
                        orderList.add(tempChar.pop());
                    }
                    tempChar.pop();  // 当 ( 弹出，消除小括号
                    break;

                case "-":
                case "+":
                case "*":
                case "/":
// 遍历到 + - * / 时，需要比较栈中已经存在的符号的优先级，将优先级高的放前面
// 当遍历到的符号，小于等于栈顶符号优先级，需要弹栈操作,直到当前符号优先级大于栈顶元素时结束
                    while (!tempChar.isEmpty() &&
                            (symbolPriority.get(s) <= symbolPriority.getOrDefault(tempChar.peek(), 0))) {
                        orderList.add(tempChar.pop());
                    }
// 比较结束后，将当前字符压入
                    tempChar.push(s);
                    break;
            }
        }

// 将剩余符号添加到栈中
        while (!tempChar.empty()) {
            orderList.add(tempChar.pop());
        }

        return orderList;
    }

// 转换为数字和符号集合，可能存在负数  -1*(-1-1)
    public static List<String> parseList(String a ) {
        List<String> list = new ArrayList<>();
        StringBuilder numStr = new StringBuilder();
        boolean lastChar = true;    // 上一个是字符（除了括号），用于判断是否存在负数

        for (int i = 0; i < a.length(); i++) {
            char ch = a.charAt(i);
            if (ch == ' ') {
                continue;
            }
            if (Character.isDigit(ch) || (ch == '-' && lastChar)) {
                numStr.append(ch);
                lastChar = false;
            } else { // 字符
                if ('(' != ch && ch != ')') {
                    lastChar = true;
                }

                if (numStr.length() > 0) {
                    list.add(numStr.toString());
                    numStr = new StringBuilder();
                }

                list.add(String.valueOf(ch));
            }
        }

        if (numStr.length() > 0)
            list.add(numStr.toString());

        return list;
    }
}