NC137 表达式求值 题解

第一次写博客 --、写的不好请各位大佬留下宝贵的意见 首先，我们应当写出无括号纯加减乘的函数：

    s += ' '   # 将表达式最后一位置为空格，说明此时已经结束，前一个运算符需要开始进行运算
    mass = ''  # 设定一个空的数字字符串对象
    int_list = []  # 存放需要累加的数字或者运算结果
    fuhao_list = []  # 保存运算符号

遍历整个无括号纯加减乘除的函数字符串

# 遇上数字，或者开头的负号以及符号的下一个负号，都作为数字传入mass
# 这个i == len(s) - 1 即为前面 s += ' '的作用
# 遇上符号为加减且前面已有运算符，或者前一个是*，或已到结尾，则计算前一个运算符，更新最近一个运算符和数字
# 最后一个elif，当遇上+-符号但是前面没有别的符号，或这个符号是*号，mass传入int_list，当前符号传入fuhao_list
    if '0' <= s[i] <= '9' or (s[i]=='-' and s[i-1] in ('+', '-','*')) or i==0:
        mass += s[i]    
    elif (s[i] in ('+', '-') and len(fuhao_list) > 0) or (len(fuhao_list) > 0 and fuhao_list[-1] == '*') or i == len(s)-1:
        int_list[-1] = self.fuhao(int_list[-1], mass, fuhao_list[-1])
        fuhao_list.pop()
        fuhao_list.append(s[i])
        mass = '' 
    elif (s[i] in ('+', '-') and len(fuhao_list) == 0) or (s[i] == '*'):
        fuhao_list.append(s[i])
        int_list.append(mass)
        mass = ''

遍历完之后求表达式的值

    if len(int_list)<=1:
        return int_list[-1]
    return self.fuhao(int_list[-2], int_list[-1], fuhao_list[-2])

其中符号运算函数为：

    def fuhao(self, a, b, f):
        if f == '+':
            return str(int(a) + int(b))
        elif f == '-':
            return str(int(a) - int(b))
        elif f == '*':
            return str(int(a) * int(b))

到这里，本题最麻烦的问题解决了，接下来只需要搞一个栈或者链表，我选择使用的是链表，处理括号问题，括号(则设为next node，)则用前面的函数先处理括号内的表达式，之后return前一个node

完整代码：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回表达式的值
# @param s string字符串 待计算的表达式
# @return int整型
#
class Solution:
    def solve(self, s: str) -> int:
        # write code here
        node = Node('')
        for i in range(len(s)):
            if s[i] not in ('(',')'):
                node.val += s[i]
            elif s[i] == '(':
                pre = Node('')
                pre.next = node
                node = pre
            elif s[i] == ')':
                data = self.add_diff(node.val)
                node = node.next
                node.val += data
        return int(self.add_diff(node.val))

    def add_diff(self, s):
        s += ' '
        mass = ''
        int_list = []
        fuhao_list = []
        for i in range(len(s)):
            if '0' <= s[i] <= '9' or (s[i]=='-' and s[i-1] in ('+', '-','*')) or i==0:
                mass += s[i]
            elif (s[i] in ('+', '-') and len(fuhao_list) > 0) or (len(fuhao_list) > 0 and fuhao_list[-1] == '*') or i == len(s)-1:
                int_list[-1] = self.fuhao(int_list[-1], mass, fuhao_list[-1])
                fuhao_list.pop()
                fuhao_list.append(s[i])
                mass = ''
            elif (s[i] in ('+', '-') and len(fuhao_list) == 0) or (s[i] == '*'):
                fuhao_list.append(s[i])
                int_list.append(mass)
                mass = ''
        if len(int_list)<=1:
            return int_list[-1]
        return self.fuhao(int_list[-2], int_list[-1], fuhao_list[-2])

    def fuhao(self, a, b, f):
        if f == '+':
            return str(int(a) + int(b))
        elif f == '-':
            return str(int(a) - int(b))
        elif f == '*':
            return str(int(a) * int(b))
class Node():
    def __init__(self,val):
        self.val = val
        self.next = next