LeetCode 227: Basic Calculator II

Problem Restatement

We are given a string s representing a mathematical expression.

The expression contains:

• Non-negative integers
• Operators: +, -, *, /
• Spaces

We must evaluate the expression and return the integer result.

Division truncates toward zero.

LeetCode examples:

Input:  "3+2*2"
Output: 7

Input:  " 3/2 "
Output: 1

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

The expression is always valid.

Input and Output

Function shape:

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

Examples

Example 1:

s = "3+2*2"

Multiplication has higher priority:

2 * 2 = 4
3 + 4 = 7

Result:

7

Example 2:

s = "14-3/2"

Division first:

3 / 2 = 1

Integer division truncates toward zero.

Then:

14 - 1 = 13

Result:

13

Example 3:

s = "18+4*5-6/2"

Compute multiplication and division first:

4 * 5 = 20
6 / 2 = 3

Then:

18 + 20 - 3 = 35

Result:

35

First Thought: Build the Full Expression

One possible idea is:

1. Parse all numbers and operators.
2. Build an expression tree.
3. Evaluate the tree.

This works, but the problem is simpler than a full calculator parser.

We only have four operators and no parentheses.

That means we only need to handle operator precedence.

Key Insight

Addition and subtraction are low-priority operators.

Multiplication and division are high-priority operators.

We can process the expression from left to right while maintaining a stack.

The stack represents values that will eventually be added together.

Rules:

• +x → push x
• -x → push -x
• *x → pop top value, multiply, push result
• /x → pop top value, divide, push result

At the end:

answer = sum(stack)

This works because multiplication and division are resolved immediately before later addition.

Algorithm

We scan the string character by character.

Maintain:

• num: current number being built
• op: previous operator
• stack: intermediate values

Initially:

op = "+"

This means the first number behaves like a positive number.

For every character:

If the character is a digit

Extend the current number:

num = num * 10 + int(ch)

This handles multi-digit numbers.

For example:

"123"

becomes:

1
12
123

If the character is an operator or we reached the end

We process the previous operator stored in op.

If:

op == "+"

push:

num

If:

op == "-"

push:

-num

If:

op == "*"

compute immediately:

stack.pop() * num

If:

op == "/"

compute immediately:

int(stack.pop() / num)

Then:

1. Update op
2. Reset num = 0

At the end, sum the stack.

Correctness

We process the expression from left to right.

The stack always stores values that should eventually be added together.

For addition:

a + b

we simply push a, then push b.

For subtraction:

a - b

we push a, then push -b.

So subtraction becomes addition of a negative number.

Multiplication and division must happen before later additions.

When we encounter * or /, the left operand is already at the top of the stack.

So we immediately compute:

top * num

or:

top / num

and replace the old value.

This guarantees multiplication and division are resolved before the final sum.

Therefore, the final stack sum equals the correctly evaluated expression.

Complexity

Here, n is the length of the string.

Implementation

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        num = 0
        op = "+"

        for i, ch in enumerate(s):
            if ch.isdigit():
                num = num * 10 + int(ch)

            if ch in "+-*/" or i == len(s) - 1:
                if op == "+":
                    stack.append(num)

                elif op == "-":
                    stack.append(-num)

                elif op == "*":
                    stack.append(stack.pop() * num)

                elif op == "/":
                    stack.append(int(stack.pop() / num))

                op = ch
                num = 0

        return sum(stack)

Code Explanation

We keep building the current number:

num = num * 10 + int(ch)

This supports numbers larger than one digit.

The variable op stores the operator that should be applied to num.

Initially:

op = "+"

so the first number gets pushed normally.

When we hit an operator, we process the previous operation.

For example:

elif op == "*":
    stack.append(stack.pop() * num)

Suppose the stack top is 3 and num = 4.

Then:

3 * 4 = 12

and 12 replaces the old stack value.

Division uses:

int(stack.pop() / num)

because LeetCode requires truncation toward zero.

At the end:

return sum(stack)

All multiplication and division are already resolved, so simple addition gives the final answer.

Testing

def run_tests():
    s = Solution()

    assert s.calculate("3+2*2") == 7
    assert s.calculate(" 3/2 ") == 1
    assert s.calculate(" 3+5 / 2 ") == 5
    assert s.calculate("14-3/2") == 13
    assert s.calculate("18+4*5-6/2") == 35
    assert s.calculate("42") == 42
    assert s.calculate("100/10*5") == 50
    assert s.calculate("1-1+1") == 1

    print("all tests passed")

run_tests()