0772：基本计算器 III（★★）

Ian

2017-02-10 约 354 字预计阅读 1 分钟次阅读

力扣第 772 题

题目

实现一个基本的计算器来计算简单的表达式字符串。

表达式字符串只包含非负整数，算符 +、-、*、/ ，左括号 ( 和右括号 ) 。整数除法需要 向下截断 。

你可以假定给定的表达式总是有效的。所有的中间结果的范围均满足 [-2³¹, 2³¹ - 1] 。

注意：你不能使用任何将字符串作为表达式求值的内置函数，比如 eval() 。

示例 1：

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

示例 2：

输入：s = "6-4/2"
输出：4

示例 3：

输入：s = "2*(5+5*2)/3+(6/2+8)"
输出：21

提示：

1 <= s <= 10⁴
s 由整数、'+'、'-'、'*'、'/'、'(' 和 ')' 组成
s 是一个 有效的 表达式

分析

0224 升级版，用双栈+优先级运算即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def calculate(self, s: str) -> int:
        func = {'+': int.__add__, '-': int.__sub__, '*': int.__mul__, '/': lambda x, y: int(x/y)}
        pro =  dict(zip('(+-*/', [0, 1, 1, 2, 2]))
        stack, ops = [], []
        for left, num, op, right in re.findall(r'(\()|(\d+)|([-+*/])|(\))', s + '+'):
            if left:
                ops.append(left)
            elif num:
                stack.append(int(num))
            elif op:
                while ops and pro[ops[-1]] >= pro[op]:
                    b, a = stack.pop(), stack.pop()
                    stack.append(func[ops.pop()](a, b))
                ops.append(op)
            else:
                while ops[-1] != '(':
                    b, a = stack.pop(), stack.pop()
                    stack.append(func[ops.pop()](a, b))
                ops.pop()
        return stack[0]

48 ms

目录

0772：基本计算器 III（★★）

题目

分析

解答