Basic Calculator II
Asked at Apple
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple 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.
Visual walkthrough for "3+22":
i=0: num=3, char=+. operator=+. Push 3. Stack=[3].
i=2: num=2, char=. operator=. Push 2. Stack=[3, 2].
i=4: num=2, end. operator=. Pop 2, 2*2=4. Push 4. Stack=[3, 4].
Sum stack: 3+4=7. Result: 7.
For " 3/2 ": num=3, char=/. Pop 3, 3/2=1 (integer). Push 1. Stack=[1]. num=2, end. Push 2. Wait - need to process / for 2.
Actually: i=0: num=3. i=2: char=/. Process /: pop nothing yet... Let me re-trace.
i=0: build num=3. i=2: /. Process last_op=+ (initial): push 3. Stack=[3]. num=2. i=4: end. Process /: pop 3, 3/2=1. Push 1. Stack=[1]. Result: 1.
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 -).
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Basic Calculator II?
Basic Calculator II is asked at Apple. 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 /).