题解 | 表达式求值

import java.util.*;
public class Solution {
    public int solve(String s) {
        // 用于存储运算符
        LinkedList<Character> operator_stack = new LinkedList<>();
        // 用于存储数字
        LinkedList<Integer> num_stack = new LinkedList<>();
        int num = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 如果当前字符是数字
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
                // 如果是计算式的最后一位或者后面一位不是数字
                if (i + 1 == s.length() || !Character.isDigit(s.charAt(i + 1))) {
                    num_stack.addLast(num);
                    num = 0;
                }
            }
            // 如果当前字符不是数字
            if (!Character.isDigit(c)) {
                if (c == '(') {
                    operator_stack.addLast(c);
                } else if (c == ')') {
                    // 遇到）时准备计算括号内表达式
                    while (operator_stack.peekLast() != '(') {
                        calculate(num_stack, operator_stack);
                    }
                    // 把左括号出栈
                    operator_stack.removeLast();
                } else {
                    // 当前运算符优先级低于或等于运算符栈中等待运算的运算符
                    while (!operator_stack.isEmpty() &&
                            getPriority(c) <= getPriority(operator_stack.peekLast())) {
                        calculate(num_stack, operator_stack);
                    }
                    // 将当前运算符入栈
                    operator_stack.addLast(c);
                }
            }
        }
        // 当运算符栈中还有运算符时，继续进行计算
        while (!operator_stack.isEmpty()) {
            calculate(num_stack, operator_stack);
        }
        // 最后数字栈中剩下的唯一元素就是计算结果
        return num_stack.removeLast();
    }

    // 用于定义运算符的优先级，乘法的优先级高于加法和减法，括号的优先级最低。
    public int getPriority(char operator) {
        if (operator == '+' || operator == '-') {
            return 1;
        }
        if (operator == '*') {
            return 2;
        }
        return -1;
    }

    // 用于执行具体的计算操作，从数字栈中弹出两个操作数，从运算符栈中弹出一个运算符，进行相应的计算，并将结果压入数字栈。
    public void calculate(LinkedList<Integer> num_stack,
                          LinkedList<Character> operator_stack) {
        int b = num_stack.removeLast();
        int a = num_stack.removeLast();
        char operator = operator_stack.removeLast();
        int result = 0;
        if (operator == '+') {
            result = a + b;
        } else if (operator == '-') {
            result = a - b;
        } else if (operator == '*') {
            result = a * b;
        }
        num_stack.addLast(result);
    }
}