AlgoMaster Logo

Basic Calculator II

Last Updated: April 1, 2026

medium
5 min read

Understanding the Problem

We need to evaluate a mathematical expression containing the four basic arithmetic operators (+, -, *, /) along with spaces and non-negative integers. No parentheses this time, which simplifies things compared to Basic Calculator. But the real challenge here is operator precedence: multiplication and division must be evaluated before addition and subtraction.

Consider 3+2*2. If we just evaluate left to right, we get (3+2)*2 = 10, which is wrong. The correct answer is 3+(2*2) = 7 because * binds tighter than +.

So the core question is: how do we respect operator precedence in a single pass through the string? The key observation is that when we see a + or -, we cannot immediately compute because the next number might be involved in a * or /. But when we see * or /, we can compute immediately because nothing has higher precedence. This asymmetry is what drives the solution.

Key Constraints:

  • 1 <= s.length <= 3 * 10^5 → We need an O(n) solution. Parsing the string multiple times or using heavy recursion with repeated substring operations would be too slow.
  • s consists of digits, +, -, *, /, and spaces → We need to skip whitespace and parse multi-digit numbers.
  • All integers are non-negative → No unary minus to worry about, which simplifies parsing.
  • Integer division truncates toward zero → In Java and C++, integer division already truncates toward zero. In Python, we need to be careful because // rounds toward negative infinity, so we should use int(a / b) instead.

Approach 1: Stack-Based Evaluation

Intuition

The most natural way to handle operator precedence is to use a stack. The idea is simple: we process the expression left to right, and whenever we encounter + or -, we push the current number (with its sign) onto the stack. We defer the final summation until the end. But when we encounter * or /, we pop the top of the stack, compute immediately, and push the result back. This way, all multiplications and divisions are resolved as soon as they appear, while additions and subtractions are collected and summed at the end.

Why does this work? Because * and / only ever involve two operands: the number right before them (which is on top of the stack) and the number right after them (which we just parsed). By computing them immediately, we ensure they take precedence over the pending + and - operations waiting in the stack.

Algorithm

  1. Initialize a stack, a variable currentNum to build multi-digit numbers, and a variable prevOp set to '+' (because the first number is implicitly preceded by addition).
  2. Iterate through each character in the string.
  3. If the character is a digit, extend currentNum by multiplying by 10 and adding the digit.
  4. If the character is an operator or we have reached the end of the string, process the number based on prevOp:
    • If prevOp is '+', push currentNum onto the stack.
    • If prevOp is '-', push -currentNum onto the stack.
    • If prevOp is '*', pop the stack, multiply by currentNum, push the result.
    • If prevOp is '/', pop the stack, divide by currentNum (truncating toward zero), push the result.
  5. Update prevOp to the current operator, and reset currentNum to 0.
  6. After processing all characters, sum everything in the stack. That is the answer.

Example Walkthrough

1Initialize: currentNum=0, prevOp='+', scan from left
0
3
i
1
+
2
2
3
*
4
2
1/7
1Stack empty, prevOp='+'
1/7

Code

The stack approach works well but we never look deeper than the top element. Since we only ever modify the top of the stack, we can replace it with just two variables and eliminate the extra space entirely.

Approach 2: Optimized Without Stack (O(1) Space)

Intuition

Since there are no parentheses, we only have two levels of precedence: *// (high) and +/- (low). When we encounter * or /, we immediately compute with the previous number. When we encounter + or -, the previous number is "finalized" and can be added to the running result.

So we track two things: result (the accumulated sum of all finalized terms) and lastNum (the most recent term that might still be involved in a * or /). When we see + or -, we know lastNum is done, so we add it to result and start a new term. When we see * or /, we update lastNum by multiplying or dividing it with the next number.

This is essentially what the stack was doing, but since we only ever touch the top, two variables are enough.

Algorithm

  1. Initialize result = 0, lastNum = 0, currentNum = 0, and prevOp = '+'.
  2. Iterate through each character in the string.
  3. If the character is a digit, extend currentNum.
  4. If the character is an operator or we are at the end of the string:
    • If prevOp is '+', add lastNum to result, set lastNum = currentNum.
    • If prevOp is '-', add lastNum to result, set lastNum = -currentNum.
    • If prevOp is '*', set lastNum = lastNum * currentNum.
    • If prevOp is '/', set lastNum = lastNum / currentNum (truncate toward zero).
  5. Update prevOp to the current operator, reset currentNum = 0.
  6. After the loop, return result + lastNum (don't forget the last term).

Example Walkthrough

1Initialize: result=0, lastNum=0, currentNum=0, prevOp='+'
0
1
i
1
4
2
-
3
3
4
/
5
2
1/7
1All variables initialized
result
:
0
lastNum
:
0
currentNum
:
0
prevOp
:
+
1/7

Code