227. Basic Calculator II
Asked at Apple, TikTok
Difficulty
Medium
Time
O(n)
Space
O(n)
Pattern
Math
Companies
2
Problem
You are given a string s that holds a valid arithmetic expression. It contains non-negative integers and the four operators +, -, *, /. Spaces may appear anywhere between the tokens. There are no parentheses.
Evaluate the expression and return the integer result. Normal math precedence applies: * and / are done before + and -. When two operators have the same precedence, work from left to right.
Division is integer division that truncates toward zero. For example, 7/2 is 3 and -7/2 is -3. You may not call a built-in function that evaluates a string as an expression (like eval).
What we must evaluate
Constraints
- ●
1 <= s.length <= 3 * 10^5 - ●
s contains integers and the operators '+', '-', '*', '/' separated by some number of spaces. - ●
s is always a valid expression. - ●
All integers in s are non-negative and in the range [0, 2^31 - 1]. - ●
The final answer fits in a 32-bit integer.
Examples
s = "3+2*2"7s = " 3/2 "1s = " 3+5 / 2 "5Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
| TikTok | Medium | View all TikTok questions → |
How to Think About It
Brute force: parse all tokens, then do two passes - first for * and /, then for + and -. That's O(n) but requires extra storage. A stack-based approach is cleaner.
Key insight: use a stack to handle operator precedence. Push numbers onto the stack. When you see + or -, push the number (or its negative). When you see * or /, pop the top, compute, and push the result. At the end, sum the stack.
Why this works: * and / have higher precedence and are left-associative. By processing them immediately (pop-compute-push), you resolve them before dealing with + and -. The stack holds intermediate values that will be summed at the end.
Implementation: track the current number and the last operator. For each character, build the number. When you hit an operator or end of string, process the last operator: +push num, -push -num, *pop and multiply and push, /pop and divide and push. Update last operator.
Edge cases: spaces in the string (skip them), division truncates toward zero (use int()), negative numbers at the start, single number (no operators).
Optimal Approach
Step 1: Initialize stack, current number = 0, last operator = '+'.
Step 2: For each character (including a sentinel at the end):
- If digit: current = current * 10 + digit.
- If operator or end of string:
- If last op was '+': push current.
- If last op was '-': push -current.
- If last op was '*': pop top, multiply by current, push result.
- If last op was '/': pop top, divide by current (truncate toward zero), push result.
- Update last operator and reset current.
Step 3: Sum all values on the stack.
Walkthrough for "3+2*2":
- start: stack=[], num=0, op=+
- '3': num=3.
- '+': push 3. stack=[3]. op=+. num=0.
- '2': num=2.
- '': push 2. stack=[3,2]. op=. num=0.
- '2': num=2.
- end: process : pop 2, 22=4. push 4. stack=[3,4].
- Sum: 3+4=7.
Time: O(n) - single pass. Space: O(n) for the stack in worst case (all + and -).
Stack resolves precedence on the fly
What Trips People Up in Real Interviews
Using float division instead of integer division. The problem says truncate toward zero. In Python, int(val / num) truncates toward zero. Using val // num truncates toward negative infinity, which is wrong for negative numbers.
Trying to evaluate left to right without handling operator precedence. Multiplication and division must happen before addition and subtraction. The stack handles this naturally.
Forgetting to handle the last number. The loop processes operators, so the final number after the last operator must be handled with a sentinel check (i == len(s) - 1).
Not handling spaces. The input string can contain spaces. Skip them: if ch == ' ': continue or just check ch.isdigit() and ch in '+-*/'.
Popping from an empty stack. This should not happen with valid input, but be defensive. In this problem, the stack always has at least one element when you pop (because a number was pushed before any * or /).
Solution Code
O(n) timedef calculate(s):
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 == '/':
val = stack.pop()
stack.append(int(val / num))
op = ch
num = 0
return sum(stack)Frequently Asked Questions
What is the Basic Calculator II problem?
Given a string s representing an arithmetic expression with +, -, *, / and no parentheses, evaluate it and return the result. This problem tests your ability to handle operator precedence and parse strings carefully.
How do you solve Basic Calculator II?
The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Basic Calculator II?
Basic Calculator II is asked at Apple, TikTok. It is a medium difficulty problem.
What are common mistakes on Basic Calculator II?
- Using float division instead of integer division. The problem says truncate toward zero. In Python, `int(val / num)` truncates toward zero. Using `val // num` truncates toward negative infinity, which is wrong for negative numbers.
- Trying to evaluate left to right without handling operator precedence. Multiplication and division must happen before addition and subtraction. The stack handles this naturally.
- Forgetting to handle the last number. The loop processes operators, so the final number after the last operator must be handled with a sentinel check (i == len(s) - 1).
- Not handling spaces. The input string can contain spaces. Skip them: `if ch == ' ': continue` or just check `ch.isdigit()` and `ch in '+-*/'`.
- Popping from an empty stack. This should not happen with valid input, but be defensive. In this problem, the stack always has at least one element when you pop (because a number was pushed before any * or /).