目录

0224:基本计算器(★★)

力扣第 224 题

题目

给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数,比如 eval()

示例 1:

输入:s = "1 + 1"
输出:2

示例 2:

输入:s = " 2-1 + 2 "
输出:3

示例 3:

输入:s = "(1+(4+5+2)-3)+(6+8)"
输出:23

提示:

  • 1 <= s.length <= 3 * 105
  • s 由数字、'+''-''('')'、和 ' ' 组成
  • s 表示一个有效的表达式
  • '+' 不能用作一元运算(例如, "+1""+(2 + 3)" 无效)
  • '-' 可以用作一元运算(即 "-1""-(2 + 3)" 是有效的)
  • 输入中不存在两个连续的操作符
  • 每个数字和运行的计算将适合于一个有符号的 32位 整数

相似问题:

分析

四则运算有个通用的方法:

  • 用一个栈 sk 维护数字,一个栈 ops 维护运算符
  • 遍历到某个运算符时,将前面优先级更高的运算符从 ops 弹出,先运算
    • 比如遇到 ‘+-’ 时,可以将 ops 栈顶的 ‘+-*/’ 先运算
  • 遇到 ‘)’ 时,一直弹出 ops 的运算符,直到栈顶为 ‘(’ 为止
  • 注意 s 末尾添加一个加号,让所有运算符都出栈

注意本题的’-‘可以用作一元运算,观察发现只有当 ‘-’ 在开头或在 ‘(’ 后面时才是一元运算,所以用 pre 保存上一个遍历元素,特判即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def calculate(self, s: str) -> int:
        func = {'+':int.__add__,'-':int.__sub__}
        pro = dict(zip('+-(','113'))
        sk,ops = [],[]
        pre = '('
        for x,op in re.findall('(\d+)|([-+*/()])',s+'+'):
            if x:
                sk.append(int(x))
            elif op=='(':
                ops.append(op)
            elif op==')':
                while ops[-1] != '(':
                    b,a = sk.pop(),sk.pop()
                    sk.append(func[ops.pop()](a,b))
                ops.pop()
            else:
                if op=='-' and pre=='(':
                    sk.append(0)
                while ops and pro[ops[-1]]<=pro[op]:
                    b,a = sk.pop(),sk.pop()
                    sk.append(func[ops.pop()](a,b))
                ops.append(op)
            pre = x or op
        return sk.pop()

122 ms