↓Skip to main content
  1. Posts/

LeetCode-772 基本计算器 III

·1 min·
Table of Contents

LeetCode-772 基本计算器 III #

Solution 1 #

使用两个栈分别保存读取到的数字和运算符. 遍历字符串, 处理如下:

  • 遇到左括号: 入栈.
  • 遇到右括号, 一路运算到左括号为止.
  • 遇到运算符, 如果当前栈顶运算符优先级相同或更高, 就计算栈顶的运算, 直到遇到优先级更低的运算符或者左括号为止. 再将这个运算符入栈.
  • 遇到数字, 完整读取这个数字并入栈.

遍历字符串之后, 将剩余的运算符一并运算完.

代码如下:

class Solution:
    def calculate(self, s: str) -> int:
        def calc(nums, ops) -> None: 
            if len(nums) <= 1:
                return
            if not ops:
                return
            b = nums.pop()
            a = nums.pop()
            op = ops.pop()
            res = 0
            if op == '+':
                res = a + b
            elif op == '-':
                res = a - b
            elif op == '*':
                res = a * b
            else:
                res = a // b
            nums.append(res)

        nums, ops = [], []
        op_lv = {'+': 1, '-':1, '*': 2, '/': 2}
        s = '0' + s.replace(' ', '')
        n = len(s)
        i = 0
        while i < n:
            ch = s[i]
            if ch == '(':
                ops.append(ch)
            elif ch == ')':
                while ops:
                    if ops[-1] != '(':
                        calc(nums, ops)
                    else:
                        ops.pop()
                        break
            elif ch.isdigit():
                r = 0
                j = i
                while j < n and s[j].isdigit():
                    r = r * 10 + int(s[j])
                    j += 1
                nums.append(r)
                i = j - 1
            else:
                while ops and ops[-1] != '(':
                    prev = ops[-1]
                    if op_lv[prev] >= op_lv[ch]:
                        calc(nums, ops)
                    else:
                        break
                ops.append(ch)
            i += 1
        while ops:
            calc(nums, ops)
        return nums[-1]

Solution 1 #

代码如下:

↑