题解 | #表达式求值#

表达式求值

https://www.nowcoder.com/practice/c215ba61c8b1443b996351df929dc4d4

以"2*(3-3-2*3) "为例，

问题可拆解为：

① 计算所有括号内表达式 [递归] ，初始表达式可在左右两侧加括号，视为"( 2*(3-3-2*3) )"；

② 计算多个值累加，每个表达式可视为多元素累加 [列表储存]。元素包括：乘积结果，eg. 2*3 视为 +(2*3)；被减数的相反数，eg. -3记为+(-3）；加数与被加数。即在列表内存储 [3, -3, -6=(-2)*3]，累加；

③ 计算乘法；

④ 获取数字，eg. '11'。

具体方法：

表达式s从前至后依次处理，当s长度为0时，程序结束。为方便理解，由④至①倒序说明。

④ 获取数字

s=‘（11*(3-1) )’，获取11，更新后字符串为s='*(3-1)';

③ 乘法

s=‘（11*(3-1) )’

将数字11入栈，判断更新后字符串第一个元素为“*”，栈顶11出栈并与括号内运算结果（）相乘，相乘结果入栈；

② 累加

每个括号对应一个栈，栈内保存的确定元素一定是取反后、乘积、子括号内表达式的值，确定元素指除了栈顶的其余元素（栈顶可能参与后续运算：乘法）。

新调用递归函数，第一个字符为数值，提取数字后入栈；

接下来运算符为“-”，提取后面数字或括号表达式的值，取相反数后入栈；

运算符为“*”，提取后面数字或括号表达式的值，将栈顶出栈并与之相乘，乘积入栈；

接下来运算符为“+”，提取后面数字或括号表达式的值，入栈。

① 计算括号内的表达式

识别到 “(”【记为'(1'】，说明遇到新的括号，调用递归函数，将该 "(" 后的字符串【记为‘s1’】传入；识别到数字，根据②计算；后续根据②③④提到的场景计算。

遇到 ')'，最内层子括号结束计算，返回最内层子括号表达式的值，并将该值入栈（倒数第二层子括号表达式对应的栈）；依次迭代，直到最外层括号（初始表达式）计算完成。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回表达式的值
# @param s string字符串 待计算的表达式
# @return int整型

class Solution:
    def solve(self , s: str) -> int:
        class Stack(object):
            def __init__(self) -> None:
                self.item = []

            def push(self, node):
                self.item.append(node)

            def pop(self):
                return self.item.pop()

            def top(self):
                return self.item[-1]

            def isEmpty(self):
                if self.item == []:
                    return True
                else:
                    return False

        def get_num(item, s) -> tuple():
            li = [int(item)]
            while s:
                if s[0].isdigit():
                    li.append(int(s[0]))
                    s = s[1:]
                else:
                    break
            num = 0
            for i in range(len(li)):
                num += li[i] * 10 ** (len(li)-i-1)
            return num, s

        def cal_bracket(s) -> tuple():
            stack_str = Stack()
            stack_num = Stack()
            while s:
                item, s = s[0], s[1:]
                if item == '(':
                    num, s = cal_bracket(s)
                    stack_num.push(num)
                elif item == ')':
                    return (sum(stack_num.item), s) # 本cal_bracket结束，返回: ()计算值，新的s
                elif item == '*':
                    if s[0] == '(':
                        num, s = cal_bracket(s[1:])
                        stack_num.push(stack_num.pop() * num)
                    elif s[0].isdigit():
                        num, s = get_num(s[0], s[1:])
                        stack_num.push(stack_num.pop() * num)
                elif item == '+':
                    pass
                elif item == '-':
                    if s[0] == '(':
                        num, s = cal_bracket(s[1:])
                        stack_num.push(-num)
                    elif s[0].isdigit():
                        num, s = get_num(s[0], s[1:])
                        stack_num.push(-num)
                elif item.isdigit():
                    num, s = get_num(item, s)
                    stack_num.push(num)


        s = s + ')'
        return cal_bracket(s)[0]