Basic Calculator II

See all coding puzzles and patterns here.

Leetcode 227
Difficulty: Medium
Patterns:
- Stack

Problem Definition

Given a string representing a math expression, evaluate the expression and return its value. Integer division should truncate toward 0.

Examples

Some test cases to verify our solution.

assert evaluate("1+2+3") == 6
assert evaluate("4/2 + 3/3") == 3
assert evaluate("2 * 3 * 4 + 1 * 5") == 29
assert evaluate("1/2 + 4/8") == 0 # due to truncation toward zero during division

Non-Stack Solution

We'll traverse the string and maintain a result value to which we will add all multiplication-and-division terms - e.g., for $3+4 \cdot 5+8/9$, the result sequence will be: ${0, 3, 23, 24}$.

We will continue combining all multiplication and division operations to the current group until we hit the end of the string or a plus or minus, at which point, we will add the current group to the result.

def evaluate(s: str) -> int:
    s_len = len(s)

    def skip_spaces(idx):
        if idx >= s_len or s[idx] != " ":
            return idx
        idx = idx + 1
        while idx < s_len and s[idx] == " ":
            idx += 1
        return idx

    NUMS = {str(i) for i in range(10)}
    def get_num(idx):
        idx = skip_spaces(idx)
        end = idx + 1
        while end < s_len and s[end] in NUMS:
            end += 1
        return int(s[idx:end]), skip_spaces(end)

    def get_op(idx):
        idx = skip_spaces(idx)
        return s[idx], skip_spaces(idx + 1)

    res = 0
    curr, idx = get_num(0)
    while idx < s_len:
        op, idx = get_op(idx)
        if op == "+":
            res += curr
            curr, idx = get_num(idx)
        elif op == "-":
            res += curr
            tup = get_num(idx)
            curr = -tup[0]
            idx = tup[1]
        elif op == "*":
            num, idx = get_num(idx)
            curr *= num
        else:
            num, idx = get_num(idx)
            curr = int(curr / num)
    return res + curr

Non-Stack Solution Complexity

Let $n = $ len(s).

Then runtime complexity should be $\Theta(n)$ since we are processing each character only once.

Auxiliary space complexity should be $\Theta(1)$ since we are storing only a few scalars.

Stack Solution

We can maintain a stack of items that will be added together. We will maintain a running product of the current item and upon every plus or minus character, we will append the current running product to our stack. At the end, we'll sum the elements in the stack to compute our result.

This solution is basically the same as the previous solution, except that it uses significantly more memory, but can be modified to support the more difficult problem Basic Calculator.

def evaluate_stack(s: str) -> int:
    stack = []
    num = 0
    division = False
    negative = False
    res = 1
    OPS = {"*", "/", "+", "-"}
    for c in s + "+":
        if c in OPS:
            if division:
                res = int(res / num)
            else:
                res = res * num
            if c == "/":
                division = True
            elif c == "*":
                division = False
            else:
                if negative:
                    stack.append(-res)
                else:
                    stack.append(res)
                if c == "-":
                    negative = True
                else:
                    negative = False
                division = False
                res = 1
            num = 0
        elif c != " ":
            num = num * 10 + int(c)
    return sum(stack)

Stack Solution Complexity