Log inSign up
hardLeetCodeNot Started

Basic Calculator III

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

Stack
Solve on LeetCode
Lesson

Problem Statement

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, arithmetic operators +, -, *, /, and open ( and closing ) parentheses. All intermediate and final calculations fit in a standard 32-bit signed integer.

Integer division should truncate toward zero. You may assume that the given expression is always valid and contains no leading or trailing whitespaces around operators/parentheses.

Example 1 · Expression with Parentheses and Mixed Precedence:

Input: s = "2*(5+5*2)/3+(6/2+8)"
Output: 21
Explanation: 2 * (5 + 10) / 3 + (3 + 8) = 2 * 15 / 3 + 11 = 30 / 3 + 11 = 10 + 11 = 21

Example 2 · Nested Parentheses with Negative Result:

Input: s = "(2+6*3+5-(3*14/7+2)*5)+3"
Output: -12
Explanation: Parentheses inner evaluations yield -12 after final operations.

Example 3 · Single Value:

Input: s = "0"
Output: 0
Explanation: Single number evaluates to itself.

Constraints:

  • 1 <= s.length <= 104
  • s consists of digits, +, -, *, /, (, and ).
  • s is a valid arithmetic expression.
  • The result and all intermediate results fit in a 32-bit signed integer.

What You'll Learn

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

  • Master recursive descent parsing for hierarchical nested expressions.
  • Learn to manage operator precedence efficiently with stack data structures.
  • Handle multi-language integer division truncation nuances.

Pattern Recognition Trigger

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

Signals to Look For:

  • Arithmetic expression with nested parentheses ()
  • Mixed operator precedence (+, -, *, /)
  • Standard BODMAS/PEMDAS evaluation rules

Algorithmic Decision Tree:

  • Whenever ( is seen, recurse to compute inner sub-expression.
  • When * or / is seen, immediately pop stack top, compute, and push back.
  • When + or - is seen, push signed number onto stack for final summation.

Connected Patterns:

Shunting Yard AlgorithmRecursive Descent ParsingRPN Evaluation

1. Recursive String Replacement (Inner Parentheses First)

Intuition

Scan the string for the innermost matching pair of parentheses (...). Extract the substring and evaluate using standard basic calculator without parentheses. Replace the (...) slice with the computed string value. Repeat until no parentheses remain, then evaluate the remaining flat expression.

When to apply: Useful as a conceptual baseline or small prototype when string length is small (N <= 100).

Algorithm

  1. While string contains (, find the first closing ) and locate its matching open (.
  2. Extract the inner substring without parentheses.
  3. Evaluate the flat expression using linear operator scanning.
  4. Replace the parenthesized segment in the original string with the computed number.
  5. Evaluate the final flat string and return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <cctype>
5
6using namespace std;
7
8class Solution {
9 int evalFlat(string s) {
10 vector<int> st;
11 char sign = '+';
12 int num = 0;
13 int n = s.length();
14 for (int i = 0; i < n; i++) {
15 char c = s[i];
16 if (isdigit(c)) num = num * 10 + (c - '0');
17 if (i == n - 1 || (!isdigit(c) && c != ' ')) {
18 if (sign == '+') st.push_back(num);
19 else if (sign == '-') st.push_back(-num);
20 else if (sign == '*') { int t = st.back(); st.pop_back(); st.push_back(t * num); }
21 else if (sign == '/') { int t = st.back(); st.pop_back(); st.push_back(t / num); }
22 sign = c;
23 num = 0;
24 }
25 }
26 int sum = 0;
27 for (int v : st) sum += v;
28 return sum;
29 }
30public:
31 int calculate(string s) {
32 while (s.find('(') != string::npos) {
33 int closeIdx = s.find(')');
34 int openIdx = s.rfind('(', closeIdx);
35 string inner = s.substr(openIdx + 1, closeIdx - openIdx - 1);
36 int val = evalFlat(inner);
37 s = s.substr(0, openIdx) + to_string(val) + s.substr(closeIdx + 1);
38 }
39 return evalFlat(s);
40 }
41};
42
43int main() {
44 Solution sol;
45 cout << sol.calculate("2*(5+5*2)/3+(6/2+8)") << endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(N^2) — String slicing and concatenation take O(N) per parenthesis level, leading to quadratic worst-case time for deeply nested expressions.
  • Space complexity: O(N^2) — Repeated intermediate string copies allocate O(N2) total memory across reductions.

2. Shunting Yard (Two Stacks: Operands & Operators)

Intuition

Maintain two stacks: nums and ops. Scan tokens. Push numbers to nums. Push ( to ops. When ) is found, apply all operators until (. When an operator is seen, pop and apply operators with greater or equal precedence before pushing current operator.

When to apply: Ideal for general-purpose mathematical parsing and interpreter engines supporting extensible operator sets.

Algorithm

  1. Initialize nums stack and ops stack.
  2. Parse multi-digit numbers and push to nums.
  3. Push ( to ops.
  4. When ) is reached, pop and apply operations until ( is popped.
  5. For operators (+, -, *, /), pop and apply while stack top precedence >= current operator precedence.
  6. Push current operator to ops.
  7. Apply remaining operators and return top of nums.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <stack>
4#include <cctype>
5
6using namespace std;
7
8class Solution {
9 int precedence(char op) {
10 if (op == '+' || op == '-') return 1;
11 if (op == '*' || op == '/') return 2;
12 return 0;
13 }
14
15 void applyOp(stack<long long>& nums, stack<char>& ops) {
16 long long b = nums.top(); nums.pop();
17 long long a = nums.top(); nums.pop();
18 char op = ops.top(); ops.pop();
19 if (op == '+') nums.push(a + b);
20 else if (op == '-') nums.push(a - b);
21 else if (op == '*') nums.push(a * b);
22 else if (op == '/') nums.push(a / b);
23 }
24
25public:
26 int calculate(string s) {
27 stack<long long> nums;
28 stack<char> ops;
29 int n = s.length();
30 for (int i = 0; i < n; i++) {
31 if (s[i] == ' ') continue;
32 if (isdigit(s[i])) {
33 long long num = 0;
34 while (i < n && isdigit(s[i])) {
35 num = num * 10 + (s[i] - '0');
36 i++;
37 }
38 i--;
39 nums.push(num);
40 } else if (s[i] == '(') {
41 ops.push(s[i]);
42 } else if (s[i] == ')') {
43 while (!ops.empty() && ops.top() != '(') applyOp(nums, ops);
44 ops.pop();
45 } else {
46 while (!ops.empty() && precedence(ops.top()) >= precedence(s[i])) applyOp(nums, ops);
47 ops.push(s[i]);
48 }
49 }
50 while (!ops.empty()) applyOp(nums, ops);
51 return nums.top();
52 }
53};
54
55int main() {
56 Solution sol;
57 cout << sol.calculate("2*(5+5*2)/3+(6/2+8)") << endl;
58 return 0;
59}

Time & Space Complexity

  • Time complexity: O(N) — Every character and operand is pushed and popped from the two stacks at most twice.
  • Space complexity: O(N) — Operands and operators require O(N) space proportional to string length.

3. Recursive Descent + Local Stack (Single Pass Optimal)

Intuition

Define a recursive helper function reading from an index pointer. Inside helper, maintain a local stack and sign = '+'. Digits accumulate into num. When ( is encountered, recurse to evaluate the nested group into num. When an operator, ), or end-of-string is reached, push or calculate based on sign. On ), return stack sum.

When to apply: Best overall method: clean recursive divide-and-conquer structure with minimal code complexity and O(N) performance.

Algorithm

  1. Create helper(index) with local stack = [], sign = '+', and num = 0.
  2. While index < length:
  3. - If digit, accumulate num = num * 10 + digit.
  4. - If (, set num = helper(index) to evaluate inner expression.
  5. - If operator or end-of-expression:
  6. - If sign is +, push num.
  7. - If sign is -, push -num.
  8. - If sign is *, pop top, multiply with num, push back.
  9. - If sign is /, pop top, divide by num (truncated), push back.
  10. - Update sign = current_char, reset num = 0.
  11. - If ), break loop and return sum of local stack.
  12. Return sum of stack.

Recursive Descent Stack Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Parse '2', sign is '+'
Visual state
Values and pointers at this exact step
stack
TOP
2
Push adds to the top · Pop removes from the top
Variables at this step
currentNum
0
sign
*
index
2
Why this step matters

Parse 2, sign is +. Push 2 to outer stack.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <numeric>
5#include <cctype>
6
7using namespace std;
8
9class Solution {
10 int helper(const string& s, int& i) {
11 vector<int> st;
12 char sign = '+';
13 int num = 0;
14 int n = s.length();
15
16 while (i < n) {
17 char c = s[i++];
18 if (isdigit(c)) {
19 num = num * 10 + (c - '0');
20 }
21 if (c == '(') {
22 num = helper(s, i);
23 }
24 if (i == n || (!isdigit(c) && c != ' ')) {
25 if (sign == '+') st.push_back(num);
26 else if (sign == '-') st.push_back(-num);
27 else if (sign == '*') {
28 int top = st.back();
29 st.pop_back();
30 st.push_back(top * num);
31 } else if (sign == '/') {
32 int top = st.back();
33 st.pop_back();
34 st.push_back(top / num);
35 }
36 sign = c;
37 num = 0;
38 }
39 if (c == ')') break;
40 }
41
42 return accumulate(st.begin(), st.end(), 0);
43 }
44
45public:
46 int calculate(string s) {
47 int i = 0;
48 return helper(s, i);
49 }
50};
51
52int main() {
53 Solution sol;
54 cout << sol.calculate("2*(5+5*2)/3+(6/2+8)") << endl;
55 return 0;
56}

Time & Space Complexity

  • Time complexity: O(N) — Every character in the string is visited exactly once.
  • Space complexity: O(N) — Call stack depth and local stacks scale with the number of nested parentheses and operators, bounded by O(N).

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive String ReplacementO(N^2)O(N^2)Find inner parentheses, evaluate and substitute string.String copying on deep nesting
2.Shunting Yard (Two Stacks)O(N)O(N)Operator and operand stacks with explicit precedence comparison.Operator stack manipulation complexity
3.Recursive Descent + Local StackOptimalO(N)O(N)Recurse on ( and evaluate local stack with previous sign.Recursion depth bounded by expression length

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting to handle multi-digit numbers properly while scanning.

Pitfall 2:

Not handling unary negative numbers at the beginning of an expression or inside parentheses.

Pitfall 3:

Failing to truncate integer division towards zero (e.g., -3 / 2 = -1, not -2).

Pitfall 4:

Not resetting the current number variable after pushing onto the stack.

Crucial Edge Cases to Validate:

  • Single Number Expression: s = 42 -> 42 (parsed and returned directly).
  • Deeply Nested Parentheses: s = ((((2+3)))) -> 5 (recursion depth handles nesting).
  • Division Resulting in Zero: s = 1/2 -> 0 (integer division truncation).
  • Unary minus inside parentheses: handled as 0 - x or signed value correctly.

Interview Tips & Best Practices

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

  1. Mention Shunting Yard and Recursive Descent: Clarify that you can either use Dijkstra's Shunting Yard with 2 stacks or Recursive Descent with 1 local stack.
  2. Watch out for Integer Division in Python and JavaScript: In Python use int(a / b), in JavaScript use Math.trunc(a / b).

Quick Comprehension Check

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

1.Why does recursive descent simplify expression parsing with parentheses?

2.How should division int(a / b) behave for negative numbers in basic calculators?

Back to DSA Sheet