NC137 表达式求值

题目描述

请写一个整数计算器，支持加减乘三种运算和括号。

示例1
输入：
"1+2"
返回值：
3

示例2
输入：
"(2(3-4))5"
返回值：
-10

示例3
输入：
"3+234-1"
返回值：
26

解题思路

整体思路
使用栈的方式，把待处理的数压入栈，根据运算符号实时取出栈里面的数进行运算。
如果需要括号，需要将括号之前的内容保存上下文，递归进入括号里面的内容。
首先需要拆字符串为char list

s = 

然后建立一个while循环，判断每一个c的类型。每判断完一个c，就把这个c从s中删掉。
1. 如果c是数字
可以用isdigit()判断是不是数字。但是因为数字不一定是个位数，所以需要将多个c合成一个完整的数num。

if ch.isdigit():
    num = num * 10 + int(ch)

2. 如果c是左括号
   把上下文存了，递归进原函数
3. 如果c不是左括号也不是数字，或者s这时候已经被删空了
   那它可能是运算符，或者“)”。注意在创建s之前，先给个初始运算符“+”。
   • 如果之前出现过运算符“+”，stack.append(num)
   • 如果之前出现过运算符“-”，stack.append(-num)
   • 如果之前出现过运算符“*”，stack.append(stack.pop() * num)

   判断完之前出现的运算符之后，如果c是“)”，需要递归回去。

最终，计算sum(stack)，得到运算结果。

解题代码

class Solution:
    def solve(self, s):
        s = 
        def dfs():
            num, stack = 0, []
            sign = "+"  # 记录上一个出现的运算符号，默认为+
            while s:
                ch = s.pop(0)
                if ch == "(":
                    num = dfs()
                if ch.isdigit():
                    num = num * 10 + int(ch)
                if not ch.isdigit() or not s:
                    if sign == "+":
                        stack.append(num)
                    elif sign == "-":
                        stack.append(-num)
                    elif sign == "*":
                        stack.append(stack.pop() * num)
                    num, sign = 0, ch
                    if ch == ")":
                        break
            return sum(stack)
        self.result = dfs()
        return self.result

执行结果

运行时间：41ms
超过47.38% 用Python 3提交的代码
占用内存：7128KB
超过2.88%用Python 3提交的代码