题解 | 表达式求值

def cal(a: int, b: int, op: str) -> int:
    """根据运算符计算两个数的值"""
    if op == "+":
        return b + a
    elif op == "-":
        return b - a  # 注意顺序，b是先弹出的数，a是后弹出的数
    elif op == "*":
        return b * a
    else:
        raise ValueError(f"不支持的运算符: {op}")

class Solution:
    def solve(self, s: str) -> int:
        num_str = ""
        # 运算符优先级字典
        precedence = {"+": 1, "-": 1, "*": 2}
        op_stack = []
        num_stack = []

        i = 0
        while i < len(s):
            char = s[i]
            if char == ' ':  # 忽略空格
                i += 1
                continue

            if char in "0123456789":
                # 如果是数字，拼接成完整的数字字符串
                num_str += char
                # 检查下一个字符是否也是数字，以处理多位数
                while i + 1 < len(s) and s[i + 1] in "0123456789":
                    num_str += s[i + 1]
                    i += 1
                # 将拼接好的数字字符串转换为整数并压入数字栈
                num_stack.append(int(num_str))
                num_str = ""  # 重置数字字符串

            elif char == "(":
                op_stack.append(char)

            elif char == ")":
                # 遇到右括号，弹出运算符并计算，直到遇到左括号
                while op_stack and op_stack[-1] != "(":
                    op = op_stack.pop()
                    a = num_stack.pop()
                    b = num_stack.pop()
                    num_stack.append(cal(a, b, op))
                op_stack.pop()  # 弹出左括号，不进行计算

            elif char in "+-*":
                # 处理负数或正数开头的情况，或者括号后紧跟负数/正数
                if i == 0 or s[i-1] == '(' or s[i-1] in "+-*":
                    if char == '-': # 如果是负号
                        num_stack.append(0)
                    # 如果是正号，可以压入0也可以忽略，这里选择压入0保持逻辑统一
                    elif char == '+':
                        num_stack.append(0)

                # 弹出优先级高于或等于当前运算符的运算符进行计算
                while op_stack and op_stack[-1] != "(" and precedence[char] <= precedence[op_stack[-1]]:
                    op = op_stack.pop()
                    a = num_stack.pop()
                    b = num_stack.pop()
                    num_stack.append(cal(a, b, op))
                op_stack.append(char)
            i += 1

        # 处理栈中剩余的运算符
        while op_stack:
            op = op_stack.pop()
            a = num_stack.pop()
            b = num_stack.pop()
            num_stack.append(cal(a, b, op))

        # 数字栈中最后剩下的就是结果
        return num_stack[0] if num_stack else 0