Basic Calculator II

Basic Calculator II

What is this problem about?

The "Basic Calculator II interview question" is a medium-level challenge that introduces operator precedence. Unlike the basic version, this one involves +, -, *, and / but usually excludes parentheses. You must ensure that multiplication and division are performed before addition and subtraction, following the standard order of operations.

Why is this asked in interviews?

Companies like Apple, Goldman Sachs, and Uber use the "Basic Calculator II coding problem" to test a candidate's ability to handle rules and constraints. It requires the candidate to maintain a temporary state to handle operations that cannot be completed until the next number is known. It’s a core test of "String interview pattern" and data structure usage.

Algorithmic pattern used

The Stack pattern is the most intuitive way to handle precedence.

1. Traverse: Scan the string character by character.
2. Current Number: Build up the full number as you encounter digits.
3. Operator Logic: When you hit an operator or the end of the string, look at the previous operator:
   • +: Push the current number onto the stack.
   • -: Push the negative of the current number (-num) onto the stack.
   • *: Pop the top from the stack, multiply it by the current number, and push the result back.
   • /: Pop the top from the stack, divide it by the current number (using integer division), and push the result back.
4. Final Step: The stack now only contains numbers to be added. Sum them all up.

Example explanation

Expression: 3 + 2 * 2

1. Initial: num = 0, last_op = '+'.
2. '3': num = 3.
3. '+': last_op was '+', push 3. num = 0, last_op = '+'.
4. '2': num = 2.
5. '*': last_op was '+', push 2. num = 0, last_op = '*'.
6. '2': num = 2.
7. End of string: last_op was '*', pop 2, multiply by 2, push 4. Stack is [3, 4]. Sum = 7.

Common mistakes candidates make

• Integer Division: Forgetting that in many languages, -3 / 2 might result in different values than expected (usually should truncate towards zero).
• Whitespace: Failing to trim or skip spaces between numbers and operators.
• Missing the last number: Forgetting to process the final number in the string because there is no operator following it.

Interview preparation tip

To save space, you can actually solve this without a stack by using a "last_number" variable to track the result of the most recent high-precedence operation. This reduces space complexity from $O(N)$ to $O(1)$.