AlgoMaster Logo

Basic Calculator II

mediumFrequency8 min readUpdated June 23, 2026

Understanding the Problem

We need to evaluate a mathematical expression containing the four basic arithmetic operators (+, -, *, /) along with spaces and non-negative integers. The expression has no parentheses, so the entire difficulty is operator precedence: multiplication and division must be evaluated before addition and subtraction.

Consider 3+2*2. Evaluating strictly left to right gives (3+2)*2 = 10, which is wrong. The correct answer is 3+(2*2) = 7 because * binds tighter than +.

How do we respect precedence while scanning left to right? When the scanner reaches a + or -, it cannot apply the operator yet, because the next number might belong to a * or / that binds tighter. When it reaches a * or /, it can apply the operator immediately, because nothing has higher precedence. The approaches below handle this asymmetry in different ways.

Key Constraints:

  • 1 <= s.length <= 3 * 10^5 → The solution should run in O(n). Repeatedly rewriting the string (evaluate one operator, rebuild the expression, repeat) would be O(n^2) and 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 appears, which simplifies parsing.
  • Integer division truncates toward zero → In Java and C++, integer division already truncates toward zero. Python's // rounds toward negative infinity, so use int(a / b) instead.

Approach 1: Shunting-Yard (Convert to RPN, Then Evaluate)

Intuition

Operator precedence and evaluation can be handled in two separate passes. Pass 1 converts the expression to Reverse Polish Notation (postfix), where each operator appears after its operands and precedence is encoded purely by position: 3+2*2 becomes 3 2 2 * +. Pass 2 evaluates the RPN sequence with a stack of numbers and needs no precedence logic at all: push each number, and for each operator, pop two operands, apply it, and push the result back.

The conversion is Dijkstra's shunting-yard algorithm. Numbers go straight to the output list. Operators wait on a separate stack, and before a new operator is pushed, every operator already on the stack with equal or higher precedence is popped to the output. Popping on equal precedence (not only strictly higher) keeps operators at the same level left-associative, which matters for - and /: in 8-3+2, the - is popped to the output before the + is pushed, so the RPN 8 3 - 2 + evaluates (8-3)+2 = 7 rather than 8-(3+2) = 3.

Algorithm

Pass 1 (convert to RPN):

  1. Create an empty output list and an empty ops stack. Assign precedence 2 to * and /, and precedence 1 to + and -.
  2. Scan the string, skipping spaces. Parse each full multi-digit number and append it to output.
  3. For an operator c, pop from ops to output while the top of ops has precedence greater than or equal to that of c, then push c.
  4. After the scan, pop any remaining operators to output. The list now holds the expression in RPN.

Pass 2 (evaluate the RPN):

  1. Scan output left to right with an empty number stack. Push each number.
  2. For each operator, pop the right operand, then the left operand, apply the operator (division truncates toward zero), and push the result.
  3. The single value left on the stack is the answer.

Example Walkthrough

For 2+3*4-5 (correct value 2 + 12 - 5 = 9), pass 1 builds the RPN sequence:

s
1Pass 1 (shunting-yard): scan tokens, output=[], ops=[]
0
2
i
1
+
2
3
3
*
4
4
5
-
6
5
ops
1ops = []
output
1output = []
1/9

Pass 2 evaluates the RPN sequence 2 3 4 * + 5 -:

rpn
1Pass 2: evaluate RPN left to right, stack=[]
0
2
i
1
3
2
4
3
*
4
+
5
5
6
-
stack
1stack = []
1/9

Code

Shunting-yard handles parentheses and any number of precedence levels with the same two rules. This problem needs less than that: with two precedence levels and no parentheses, conversion and evaluation can be fused into one scan that uses one stack.

Approach 2: Single-Pass Stack Evaluation

Intuition

The RPN detour can be skipped: with one stack of numbers, we can evaluate during the scan itself. Process the expression left to right. After a + or -, push the number that follows (with its sign) onto the stack and defer the addition; the stack accumulates one signed term per push, and the answer is their sum. After a * or /, pop the top of the stack, apply the operator with the number that follows, and push the result back, so multiplications and divisions are resolved as soon as they appear.

Computing * and / immediately is safe because they involve exactly two operands: the number right before the operator, which sits on top of the stack, and the number right after it, which we parse next. Deferring the additions to the end cannot change the result, because once each term carries its own sign, summing the terms in any order produces the same total.

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

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

Code

The scan only ever reads and replaces the top of the stack; nothing below the top is touched until the final summation. Two variables can therefore replace the stack: one for the running sum of finished terms, and one for the term still being built.

Approach 3: Two Variables (O(1) Space)

Intuition

Without parentheses, the expression is a sum of signed terms, where each term is a chain of multiplications and divisions. For example, 2+3*4/2-5 breaks down as (+2) + (+3*4/2) + (-5), which equals 2 + 6 + (-5) = 3. We track two values: result, the sum of all completed terms, and lastNum, the term currently being built, which might still grow through a * or /.

When we see + or -, the current term is complete, so we add lastNum to result and start a new term from the next number (negated after -). When we see * or /, the term is still open, so we fold the next number into it: lastNum = lastNum * currentNum or lastNum / currentNum, truncating toward zero.

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. The final term is still held in lastNum because no operator follows it.

Example Walkthrough

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

Code