227. Basic Calculator II

227

MediumStack and Expression ProcessingStackStack with deferred multiply/divide

Basic Calculator II

Evaluate a string arithmetic expression containing non-negative integers and the operators '+', '-', '*', '/' separated by optional spaces, with no parentheses. Multiplication and division have higher precedence than addition and subtraction, and integer division truncates toward zero. Return the integer result.

Open official problem prompt ↗

In plain English

Evaluate a parenthesis-free expression while respecting that '*' and '/' bind tighter than '+' and '-'.

Picture it like this

Reading a bill left to right: additions and subtractions go into a running list of line items, but a 'times' or 'divided by' immediately rewrites the last line item before you total everything.

Example

Input: s = "3+2*2"
Output: 7
Why: '*' binds tighter than '+', so 2*2 = 4 is computed first, then 3 + 4 = 7.

Constraints

1 <= s.length <= 3 * 10^5s consists of integers and the operators '+', '-', '*', '/' separated by spacess represents a valid expressionAll intermediate results fit in a 32-bit signed integerInteger division truncates toward zero

Pattern lesson

See the pattern, then code

Stack with deferred multiply/divide

↗

Stack and Expression Processing

Nested structures, matching delimiters, undo behavior, or unresolved operations.. Push +num and -num as signed terms, but for '*' and '/' pop the last term, combine it with the current number, and push the result back, so the final answer is just the sum of the stack.

New words, made simpleKnow these before the algorithm

Operator precedence: The rule that '*' and '/' are evaluated before '+' and '-'.
Additive term: A signed value that is simply summed at the end, produced by '+' and '-'.
Deferred evaluation: Delaying the final sum until all high-precedence operations have collapsed into the stack.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Two-pass or full parser

More machinery than needed for two precedence levels.

First resolve all '*' and '/', then a second pass for '+' and '-', or build an operator/operand parser.

Time O(n)Space O(n)

Best choiceSingle stack with previous operator

One pass, elegantly encodes precedence in when you push versus collapse.

Push additive terms and fold multiply/divide into the top as you go, then sum.

Time O(n)Space O(n)

The rule we keep true

Invariant

The stack holds fully resolved additive terms for the expression processed so far; every '*' and '/' has already been collapsed into the term it modifies, so the answer is always the current sum plus the pending term.

Why this is correct

Reasoning

By acting on the previous operator only when the next one arrives, each number is fully known before it is combined. '+' and '-' defer to the final sum, while '*' and '/' pop the immediately preceding term and reattach the combined value, giving multiplication and division their higher precedence over the eventual addition of all terms.

The algorithm in three movesSay these aloud before coding

1Track the current number and the operator that precedes it (start with '+')

'3' with op '+': push 3 -> [3]

2When the next operator or the string end is reached, apply the previous operator

'2' with op '+': push 2 -> [3,2]

3For '+' push num, for '-' push -num

'2' with op '*': pop 2, push 2*2=4 -> [3,4]

4For '*' or '/' pop the top and push (top * num) or trunc(top / num)

sum -> 7

5Return the sum of the stack

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read'3'

2 · AskBuild number

3 · Update statenum=3, op='+'

4 · Resultnum becomes 3

Key takeaway

Additive terms are pushed; '*' and '/' immediately collapse into the top term, so the sum of the stack is the answer.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 7-8Build the number
Digits accumulate into num across multiple characters.
2
Lines 9Trigger on operator or end
Act on the previous operator when a new operator appears or the string ends, ensuring num is complete.
3
Lines 10-13Additive terms
'+' pushes num, '-' pushes -num, deferring them to the final sum.
4
Lines 14-17Collapse multiply/divide
Pop the top term and push it combined with num, giving these operators higher precedence; int(top / num) truncates toward zero.
5
Lines 18-20Advance state
Store the current operator for the next number and reset num.
6
Lines 21Sum the stack
All high-precedence work is done, so the total of the remaining additive terms is the answer.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Leading or trailing spaces and spaces between tokens
Division truncating toward zero, e.g. '14-3/2' = 13
Multi-digit numbers
An expression that is a single number
The final number, which is committed by the i == len(s)-1 condition

Common beginner mistakes

Not committing the last number because the loop needs the end-of-string trigger
Using // which floors negatives instead of int(x / num)
Skipping spaces incorrectly and treating them as operators
Forgetting that op starts as '+' so the first number is pushed
Applying the current operator instead of the previous one

Check your understanding

Why is the answer simply the sum of the stack at the end?

PyPython 3 · solution.py

Optimal

1class Solution:2    def calculate(self, s: str) -> int:3        stack: list[int] = []4        num = 05        op = '+'6        for i, c in enumerate(s):7            if c.isdigit():8                num = num * 10 + int(c)9            if c in '+-*/' or i == len(s) - 1:10                if op == '+':11                    stack.append(num)12                elif op == '-':13                    stack.append(-num)14                elif op == '*':15                    stack.append(stack.pop() * num)16                elif op == '/':17                    stack.append(int(stack.pop() / num))18                op = c19                num = 020        return sum(stack)

Time complexityO(n)Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleMicrosoftUber

Basic Calculator II

Basic Calculator II

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Stack and Expression Processing