题解 | #表达式求值#

算法：栈
1.用栈保存各部分计算的和
2.遍历表达式，使用 sign 变量记录运算符，初始化是 '+'；使用 number 变量记录字符串中的数字部分的数字值是多少
2.0 遇到空格时跳过
2.1 遇到数字时继续遍历求这个完整的数字的值，保存到 number 中
2.2 遇到左括号时递归求这个括号里面的表达式的值
先遍历找到对应的右括号，因为可能里面还嵌有多对括号，使用一个变量 counterPartition 统计括号对数直到变量为 0
2.3 遇到运算符时或者到表达式末尾时，就去计算上一个运算符并把计算结果 push 进栈，然后保存新的运算符到 sign
如果是 + ，不要计算，push 进去
如果是 - ，push 进去负的当前数
如果是 ×、÷ ，pop 出一个运算数和当前数作计算
3.最后把栈中的结果求和即可

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

def removeSpace(arr,i,n):
    # remove extra space
    while i<n:
        if arr[i].isspace(): 
            i+=1
        else:
            break
    return i
def getNum(arr,i,n):
    i = removeSpace(arr, i, n)
    if arr[i].isnumeric():
        # get a number 
        tnum = []
        while i<n:
            # is numberic
            if arr[i].isnumeric(): 
                tnum.append(arr[i])
                i+=1
            else:
                break
        tnum = int(''.join(tnum))
        return int(tnum),i
    elif arr[i]=="(":
        start = i
        brackNum = 1
        j = i+1
        while j<n:
            if arr[j]==")": brackNum -= 1
            elif arr[j]=="(": brackNum += 1
            j+=1
            if brackNum==0:
                break
        return cal(arr[i+1:j-1]), j
def getSign(arr,i,n):
    i = removeSpace(arr, i, n)
    if arr[i] == '-':
        # 减号
        return "-",i+1
    elif arr[i] == '+':
        # 加号
        return "+",i+1
    elif arr[i] == '*':
        # 乘号
        return "*",i+1
    elif arr[i].isnumeric():
        return "+",i
    elif arr[i] == '(':
        return "+",i
    else:
        return None
def cal(arr):
    res = 0
    stack = []
    i = 0 
    n = len(arr)
    while i<n:
        # read signs
        sign , i = getSign(arr, i, n)
        num , i = getNum(arr, i, n)
        if sign == '-':
            # 减号
            stack.append(-num)
        elif sign == '+':
            # 加号
            stack.append(num)
        elif sign == '*':
            # 乘号
            stack.append(stack.pop()*num)
        else:
            print("Error expression!")

    res = sum(stack)
    return res

class Solution:
    def solve(self , s ):
        # write code here
        return cal(s)