采用双栈解题

建立两个栈

number_stack：存放字符串s中的数字
sign_stack：存放字符串中的括号，运算符

遍历字符串，将字符串中表示数字和符号的部分分别压入数字栈和符号栈中。

压入数字栈的时候，如数字123，遍历字符串依次得到"1","2","3"，故需要对相应的数字乘以相应的位数转化为对应的数值1×10×10+2×10+3。

压入符号栈的时候，规则如下：

判断左括号，压入符号栈
判断右括号，计算与之匹配的左括号之间的数值运算，并将结果压入数字栈中
判断乘号，当符号栈为空的时候，直接压入符号栈；符号栈非空，且栈顶为号，弹出数字栈顶两个数字，与符号栈顶符号，进行运算，结果压入数字栈中；符号栈非空，且栈顶不为号。（此时对应一个括号内的公式，只含+-，优先级低于乘法）。
判断加减，符号栈为空，直接压入；符号栈非空，栈顶为运算符，弹出数字栈顶两个数字，与符号栈顶符号，进行运算，结果压入数字栈中（即计算此前括号内公式）；符号栈非空，栈顶不为运算符，直接压入栈中。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回表达式的值
# @param s string字符串 待计算的表达式
# @return int整型
#
class Solution:
    def solve(self, s: str) -> int:
        # write code here
        # 表达式的计算函数
        def computer(first, last, sign):
            if sign == "+":
                return first + last
            elif sign == "-":
                return first - last
            elif sign == "*":
                return first * last
            else:
                return ValueError("输入的计算符号有误")

        # 定义两个栈分别存储数字和符号
        number_stack = []
        sign_stack = []
        number = 0
        for i in range(len(s)):
            # s为字符串类型，故需要根据输入的字符串，转换为相应值的数字
            if s[i] >= '0' and s[i] <='9':
                number = number * 10 + int(s[i])
                # 此处内部的值判断不可少，需要和后面的else结合，判断是否将number压入栈
                if i + 1 < len(s) and s[i + 1] >= '0' and s[i + 1] <='9': 
                    continue
                else:
                    number_stack.append(number)
                    number = 0
            # 1.判断左括号，压入符号栈
            elif s[i] == "(":
                sign_stack.append(s[i])
            
            # 2.判断右括号，计算与之匹配的左括号之间的数值运算，并将结果压入数字栈中
            elif s[i] == ")":
                while sign_stack[-1] != "(":
                    last = number_stack.pop()
                    first = number_stack.pop()
                    sign = sign_stack.pop()
                    res = computer(first, last, sign)
                    number_stack.append(res)
                # 弹出左括号
                sign_stack.pop()
            
            # 3.1 判断乘号，当符号栈为空的时候，直接压入符号栈；
            # 3.2 符号栈非空，且栈顶为*号，弹出数字栈顶两个数字，与符号栈顶符号，进行运算，结果压入数字栈中；
            # 3.3 符号栈非空，且栈顶不为*号。（此时对应一个括号内的公式，只含+-，优先级低于乘法）
            elif s[i] in ["*"]:
                if len(sign_stack) == 0:
                    sign_stack.append(s[i])
                elif sign_stack[-1] in ["*"]:
                    while len(sign_stack) != 0 and sign_stack[-1] in ["*"]:
                        last = number_stack.pop()
                        first = number_stack.pop()
                        sign = sign_stack.pop()
                        res = computer(first, last, sign)
                        number_stack.append(res)
                    sign_stack.append(s[i])
                else:
                    sign_stack.append(s[i])
            
            # 4.1 判断加减，符号栈为空，直接压入
            # 4.2 符号栈非空，栈顶为运算符，弹出数字栈顶两个数字，与符号栈顶符号，进行运算，结果压入数字栈中（即计算此前括号内公式）；
            # 4.3 符号栈非空，栈顶不为运算符，直接压入栈中
            elif s[i] in ["+", "-"]:
                if len(sign_stack) == 0:
                    sign_stack.append(s[i])
                elif sign_stack[-1] in ["+", "-", "*"]:
                    while len(sign_stack) != 0 and sign_stack[-1] in ["+","-","*"]:
                        last = number_stack.pop()
                        first = number_stack.pop()
                        sign = sign_stack.pop()
                        res = computer(first, last, sign)
                        number_stack.append(res)
                    sign_stack.append(s[i])
                else:
                    sign_stack.append(s[i])
        
        # 最后计算不在括号内的部分
        while sign_stack:
            last = number_stack.pop()
            first = number_stack.pop()
            sign = sign_stack.pop()
            res = computer(first, last, sign)
            number_stack.append(res)
        # 返回值
        return number_stack[-1]

题解 | #表达式求值#

采用双栈解题