Log inSign up
mediumLeetCodeNot Started

Basic Calculator II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Stack
Solve on LeetCode
Lesson

Problem Statement

Given a string s which represents an expression, evaluate this expression and return its value.

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will fit in a 32-bit signed integer.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1 · Precedence of Multiplication:

Input: s = "3+2*2"
Output: 7
Explanation: 2 * 2 = 4, 3 + 4 = 7.

Example 2 · Spaces and Division:

Input: s = " 3/2 "
Output: 1
Explanation: 3 / 2 truncates toward zero to 1.

Example 3 · Mixed Operations:

Input: s = " 3+5 / 2 "
Output: 5
Explanation: 5 / 2 = 2, 3 + 2 = 5.

Constraints:

  • 1 <= s.length <= 3 * 105
  • s consists of integers and operators (+, -, *, /) separated by some number of spaces.
  • s represents a valid expression.
  • All the integers in the expression are non-negative integers in the range [0, 231 - 1].
  • The answer is guaranteed to fit in a 32-bit integer.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand how stack postponement resolves operator precedence without parsing trees.
  • Master the O(1) space optimization by replacing the stack with running lastNum and total variables.
  • Handle multi-digit integers, variable whitespace, and integer division truncation.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Algorithmic Decision Tree:

  • Maintain lastOp = '+', currNum = 0.
  • When encountering an operator or end of string i == s.length - 1:
  • If lastOp == '+' -> push currNum.
  • If lastOp == '-' -> push -currNum.
  • If lastOp == '*' -> stack.push(stack.pop() * currNum).
  • If lastOp == '/' -> stack.push(trunc(stack.pop() / currNum)).
  • Set lastOp = currChar, currNum = 0.
  • Sum stack elements at the end.

Connected Patterns:

Basic CalculatorBasic Calculator IIIEvaluate Reverse Polish Notation

1. Tokenize and Multi-Pass Reduction

Intuition

Split into tokens. In pass 1, resolve all * and / operations by splicing the array. In pass 2, resolve all remaining + and - operations.

Algorithm

  1. Step 1: Parse s into a token list of numbers and operators.
  2. Step 2: Pass 1: find * and /, compute with adjacent numbers, and replace with result.
  3. Step 3: Pass 2: compute + and - from left to right.
  4. Step 4: Return final value.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 int calculate(std::string s) {
8 std::vector<std::string> tokens;
9 int n = s.length();
10 int i = 0;
11 while (i < n) {
12 if (s[i] == ' ') { i++; continue; }
13 if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
14 tokens.push_back(std::string(1, s[i]));
15 i++;
16 } else {
17 std::string num = "";
18 while (i < n && s[i] >= '0' && s[i] <= '9') {
19 num += s[i++];
20 }
21 tokens.push_back(num);
22 }
23 }
24 // Pass 1: * and /
25 std::vector<std::string> pass1;
26 for (size_t j = 0; j < tokens.size(); j++) {
27 if (tokens[j] == "*" || tokens[j] == "/") {
28 int left = std::stoi(pass1.back()); pass1.pop_back();
29 int right = std::stoi(tokens[j + 1]);
30 int res = (tokens[j] == "*") ? (left * right) : (left / right);
31 pass1.push_back(std::to_string(res));
32 j++;
33 } else {
34 pass1.push_back(tokens[j]);
35 }
36 }
37 // Pass 2: + and -
38 int result = std::stoi(pass1[0]);
39 for (size_t j = 1; j < pass1.size(); j += 2) {
40 int right = std::stoi(pass1[j + 1]);
41 if (pass1[j] == "+") result += right;
42 else if (pass1[j] == "-") result -= right;
43 }
44 return result;
45 }
46};
47
48int main() {
49 Solution solver;
50 std::cout << "Result: " << solver.calculate("3+5 / 2") << std::endl;
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(N^2) — Tokenize string into array, perform pass 1 evaluating all * and / (splicing array in O(N)), then pass 2 evaluating + and -.
  • Space complexity: O(N) — O(N) space for tokens array.

Why Brute Force Doesn't Scale:

Unneeded heap allocations add memory overhead.

O(1) space evaluator processes 300,000 characters in <4ms with zero heap allocations.

2. Linear Precedence Stack

Intuition

Maintain lastOp initialized to '+'. High-precedence operators * and / evaluate immediately against the top of the stack, while + and - push signed numbers to be summed later.

Algorithm

  1. Step 1: Initialize stack st, currNum = 0, lastOp = '+'.
  2. Step 2: Loop through characters: accumulate digits into currNum.
  3. Step 3: When character is an operator or i == s.length - 1 (and not a space):
  4. - If lastOp == '+': st.push(currNum)
  5. - If lastOp == '-': st.push(-currNum)
  6. - If lastOp == '*': st.push(st.pop() * currNum)
  7. - If lastOp == '/': st.push(st.pop() / currNum)
  8. - lastOp = c, currNum = 0.
  9. Step 4: Sum all numbers in stack and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <stack>
4#include <numeric>
5
6class Solution {
7public:
8 int calculate(std::string s) {
9 std::stack<int> st;
10 int curr = 0;
11 char op = '+';
12 int n = s.length();
13 for (int i = 0; i < n; i++) {
14 char c = s[i];
15 if (c >= '0' && c <= '9') {
16 curr = curr * 10 + (c - '0');
17 }
18 if ((!isdigit(c) && c != ' ') || i == n - 1) {
19 if (op == '+') {
20 st.push(curr);
21 } else if (op == '-') {
22 st.push(-curr);
23 } else if (op == '*') {
24 int top = st.top(); st.pop();
25 st.push(top * curr);
26 } else if (op == '/') {
27 int top = st.top(); st.pop();
28 st.push(top / curr);
29 }
30 op = c;
31 curr = 0;
32 }
33 }
34 int total = 0;
35 while (!st.empty()) {
36 total += st.top();
37 st.pop();
38 }
39 return total;
40 }
41};
42
43int main() {
44 Solution solver;
45 std::cout << "Result: " << solver.calculate("3+2*2") << std::endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(N) — Single O(N) pass across characters with numbers pushed to stack and summed at the end.
  • Space complexity: O(N) — O(N) stack to store numbers.

3. Optimal O(1) Space Running Accumulator

Intuition

Instead of a full stack, we only ever need the *most recent term* (lastNumber). When a + or - arrives, lastNumber is added to totalResult and reset. When * or / arrives, it immediately mutates lastNumber.

Algorithm

  1. Step 1: Maintain totalResult = 0, lastNumber = 0, currentNumber = 0, operation = '+'.
  2. Step 2: Loop through characters c in s.
  3. Step 3: Accumulate digits into currentNumber.
  4. Step 4: When c is an operator or at end of string:
  5. - If operation == '+': totalResult += lastNumber, lastNumber = currentNumber.
  6. - If operation == '-': totalResult += lastNumber, lastNumber = -currentNumber.
  7. - If operation == '*': lastNumber = lastNumber * currentNumber.
  8. - If operation == '/': lastNumber = lastNumber / currentNumber.
  9. - operation = c, currentNumber = 0.
  10. Step 5: Return totalResult + lastNumber.

O(1) Space Precedence Execution Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Buffered lastNumber: 3
Visual state
Values and pointers at this exact step
stack
TOP
lastNum: 3
Push adds to the top · Pop removes from the top
Why this step matters

Buffered lastNumber: 3

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 int calculate(std::string s) {
7 int totalResult = 0;
8 int lastNumber = 0;
9 int currentNumber = 0;
10 char operation = '+';
11 int n = s.length();
12
13 for (int i = 0; i < n; i++) {
14 char c = s[i];
15 if (c >= '0' && c <= '9') {
16 currentNumber = currentNumber * 10 + (c - '0');
17 }
18 if ((!isdigit(c) && c != ' ') || i == n - 1) {
19 if (operation == '+') {
20 totalResult += lastNumber;
21 lastNumber = currentNumber;
22 } else if (operation == '-') {
23 totalResult += lastNumber;
24 lastNumber = -currentNumber;
25 } else if (operation == '*') {
26 lastNumber = lastNumber * currentNumber;
27 } else if (operation == '/') {
28 lastNumber = lastNumber / currentNumber;
29 }
30 operation = c;
31 currentNumber = 0;
32 }
33 }
34 totalResult += lastNumber;
35 return totalResult;
36 }
37};
38
39int main() {
40 Solution solver;
41 std::cout << "Result: " << solver.calculate(" 3+5 / 2 ") << std::endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass updating only two registers: lastNumber and currentResult.
  • Space complexity: O(1) — Strictly O(1) auxiliary space without storing stacks or token lists.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Tokenize and Multi-Pass ReductionO(N^2)O(N)2-pass token array reduction evaluating * and / first.Token list shifting.
2.Linear Precedence StackO(N)O(N)Stack accumulates terms; high precedence collapses top immediately.Memory allocation.
3.Optimal O(1) Space Running AccumulatorOptimalO(N)O(1)Keep only lastNumber and running totalResult registers.None (Optimal).

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using Python // on negative numbers.

Pitfall 2:

Not triggering evaluation at i == s.length - 1 for the trailing number.

Pitfall 3:

Letting spaces prematurely trigger an operator evaluation.

Crucial Edge Cases to Validate:

  • Division truncating toward zero `s = '14-3/2'` — 3/2 = 1, 14 - 1 = 13.
  • Multiple consecutive spaces `s = ' 3 + 2 * 2 '` — Spaces are skipped cleanly.
  • Single number `s = '42'` — Returns 42.
  • Operations producing negative intermediate values `s = '1-1+1'` — Evaluates to 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Start by explaining the stack-based reduction (O(N) time & space) to establish clear precedence handling.
  2. Immediately follow up with the O(1) space optimization: 'Since there are no parentheses, we only need to keep lastNumber and totalResult'.
  3. Highlight truncation toward zero and multi-digit number parsing.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How does the optimal approach achieve O(1) auxiliary space?

2.How is division truncation toward zero handled in Python for negative operands (e.g. -3 / 2)?

Back to DSA Sheet