题解 | #表达式求值#

'''
解题思路：
1、中缀表达式转为后缀表达式
2、为后缀表达式计算规则：从左到右遍历表达式的每个数字和符号，遇到的是数字就进栈，
遇到的时符号就将栈顶的两个数字出栈进行计算，然后将计算结果入栈，最终栈里的值即为计算的结果。
3、预处理：将字符串按实际物理意义，转成字符列表（含多位数和负数、空格、[]、{}）
'''
#----------------------------------------
# 输出num1 + operator + num2结果
def getvalue(num1,num2,operator):
    if operator == '+':
        return num1 + num2
    elif operator == '-':
        return num1 - num2
    elif operator == '*':
        return num1 * num2
    elif operator == '/':
        return num1 / num2
    else:
        return []

#----------------------------------------
# 优先级 operator1 >= operator2,输出真
def compare(operator1,operator2):
    if operator1 in '*/' and operator1 in '*/':
        return True
    elif operator1 in '+-' and operator1 in '+-':
        return True
    elif operator1 in '*/' and operator1 in '+-':
        return True
    elif operator1 in '+-' and operator1 in '*/':
        return False
    else:
        return []

#----------------------------------------
# 中缀表达式转为后缀表达式
# 输入L = ['0','-','1','*','(','0','-','1','-','1',')','-','3','*','(','1','-','2',')','-','3','*','4']
# 输出express= ['0',1','0','1','-','1','-','*','-','3','1','2','-','*','-','3','4','*','-']
def suffix_express(L):
    express = []                    # 后缀表达式
    stack = []                      # 存中间符号的栈
    for i in L:
        if i.isnumeric():           # 数字直接入表达式
            express.append(i)
        elif i in '+-':             # 遇到+—号，如果符号栈空，入符号栈
            if len(stack) == 0:
                stack.append(i)
            else:                   # 如果符号栈不为空，符号栈优先级大于等于当前符号的，弹出入表达式
                while stack and compare(stack[-1],i):
                    express.append(stack.pop())
                stack.append(i)     # 当前符号入符号栈
        elif i in '*/(':            # */(直接入符号栈
            stack.append(i)
        elif i in ')':              # 遇到),(之前的符号弹出入表达式
            while stack and stack[-1] != '(':
                express.append(stack.pop())
            if stack:              # 删除(
                stack.pop()
    while stack:                   # 最后栈中所有符号弹出入表达式
        express.append(stack.pop())
    return express

#----------------------------------------
# 为后缀表达式计算规则：
# 从左到右遍历表达式的每个数字和符号，遇到的是数字就进栈，遇到的时符号就将栈顶的两个数字出栈进行计算，
# 然后将计算结果入栈，最终栈里的值即为计算的结果。
# 输入express= ['0',1','0','1','-','1','-','*','-','3','1','2','-','*','-','3','4','*','-']
# 输出计算结果 = result
def compute(suffix_express):
    stack = []
    for i in suffix_express:
        if i.isnumeric():
            stack.append(i)
        elif i in '+-*/':
            n2 = stack.pop()
            n1 = stack.pop()
            stack.append(getvalue(int(n1),int(n2),i))
    if stack:
        return stack.pop()
    return []

#----------------------------------------
# 预处理：将字符串按实际物理意义，转成字符列表（含多位数和负数、空格、[]、{}）
# 输入：-1*(-1-1)-3*(1-2)-3*4
# 输出：['0','-','1','*','(','0','-','1','-','1',')','-','3','*','(','1','-','2',')','-','3','*','4']
def preprocess(L):
    B = ''
    for i in L:
        if i in '0123456789+-*/()[]{}':           # 去空格
            B += i
    B = B.replace('[','(')                        # 统一括号
    B = B.replace(']',')')
    B = B.replace('{','(')
    B = B.replace('}',')')
    L = '('+ B +')'                    # 左右加括号用于判断负号

    A = []
    tmp = ''
    for i in range(1,len(L)-1):
        if L[i] == '-' and L[i-1]=='(':        # 负号前必有括号,前加0将负号变减号
            A.append('0')
            A.append('-')
        elif L[i].isnumeric() and L[i+1].isnumeric():
            tmp += L[i]
        elif L[i].isnumeric() and not L[i+1].isnumeric():
            tmp += L[i]
            A.append(tmp)
            tmp = ''
        else:
            A.append(L[i])
    return A

String = input()
#String = '-1*(-1-1)-3*(1-2)-3*4'
#print(String)
List = preprocess(String)
#print(List)
express = suffix_express(List)
#print(express)
result = compute(express)
print(result)