227. Basic Calculator II

Problem

Given a string s which represents an expression, evaluate this expression and return its value.

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2³¹, 2³¹ - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

https://leetcode.com/problems/basic-calculator-ii/

Example 1:

Input: s = “3+2*2”
Output: 7

Example 2:

Input: s = " 3/2 "
Output: 1

Example 3:

Input: s = " 3+5 / 2 "
Output: 5

Constraints:

1 <= s.length <= 3 * 10⁵
s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
s represents a valid expression.
All the integers in the expression are non-negative integers in the range [0, 2³¹ - 1].
The answer is guaranteed to fit in a 32-bit integer.

Test Cases

1 2	class Solution: def calculate(self, s: str) -> int:

solution_test.py

import pytest

from solution import Solution
from solution2 import Solution as Solution2


@pytest.mark.parametrize('s, expected', [
    ("3+2*2", 7),
    (" 3/2 ", 1),
    (" 3+5 / 2 ", 5),

    ("14-3/2", 13),
])
@pytest.mark.parametrize('sol', [Solution(), Solution2()])
def test_solution(sol, s, expected):
    assert sol.calculate(s) == expected

Thoughts

跟 224. Basic Calculator，增加了高优先级的乘除法，但是去掉了括号和一元取反运算，其实是要简单一些。

可以直接套用 224. Basic Calculator 中的基于逆波兰表达式的计算逻辑，其中 tokenize 方法完全一样，reverse_polish 方法中的运算符表里增加 * 和 /，级别比 + 和 - 高即可，去掉关于括号、一元负号的逻辑，最后在 calculate 方法中增加乘法和除法的计算。

Code

solution.py

from typing import Iterator

Token = str|int


class Solution:
    def calculate(self, s: str) -> int:
        tokens = self.reverse_polish(self.tokenize(s))
        stack = []
        for token in tokens:
            if isinstance(token, int):
                stack.append(token)
            else:
                b, a = stack.pop(), stack.pop()
                if token == '+': stack.append(a + b)
                elif token == '-': stack.append(a - b)
                elif token == '*': stack.append(a * b)
                elif token == '/': stack.append(a // b)

        return stack[0]

    def tokenize(self, expr: str) -> Iterator[Token]:
        n = len(expr)
        left = 0
        for i, c in enumerate(expr):
            if c.isdigit():
                continue
            if left < i:
                yield int(expr[left:i]) # A number.
            if c != ' ':
                yield c # An operator.
            left = i + 1

        if left < n:
            yield int(expr[left:]) # The last number.

    def reverse_polish(self, tokens: Iterator[Token]) -> Iterator[Token]:
        ops = []
        levels= {'+': 1, '-': 1, '*': 2, '/': 2}
        for token in tokens:
            if isinstance(token, int):
                yield token
            else:
                p = levels[token]
                while ops and levels[ops[-1]] >= p:
                    yield ops.pop()
                ops.append(token)

        while ops:
            yield ops.pop()

Directly

没有括号的加减乘除混合运算也非常简单，也是相当于若干个数字相加，只不过遇到乘除法的时候，就先计算乘除法。

用数组记录所有待相加的数字，其中加号后边的数字直接放入数组，减号后边的数字取反后放入数组。如果是乘号或除号，则取出数组末尾的数字，跟运算符后边的数字相乘或相除，再把结果放回数组。最终对数组求和即可。

需要小心的是负数的除法。题目要求的是除法运算的结果只保留整数部分，即 3 / 2 = 1.5 → 1、-3 / 2 = -1.5 → -1。但 Python 中的整除运算（//）不符合这个要求（-3 // 2 = -2），需要用 math.trunc 函数，trunc(-3 / 2) = -1。

solution2.py

from math import trunc


class Solution:
    def calculate(self, s: str) -> int:
        vals = []
        num = 0
        prev_op = '+' # Default to `+`, means the 1st number is positive.
        n = len(s)
        for i in range(n + 1):
            c = s[i] if i < n else '='
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == ' ':
                continue
            else:
                if prev_op == '+':
                    vals.append(num)
                elif prev_op == '-':
                    vals.append(-num)
                elif prev_op == '*':
                    vals.append(vals.pop() * num)
                else:
                    vals.append(trunc(vals.pop() / num))

                prev_op = c
                num = 0

        return sum(vals)