0224：基本计算器（★★）

2015-08-12 约 539 字预计阅读 2 分钟次阅读

力扣第 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 * 10⁵
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

目录

0224：基本计算器（★★）

题目

分析

解答