Basic Calculator II solution and explanation
9 more videos on this problem
BASIC CALCULATOR II | LEETCODE 227 | PYTHON SOLUTIONCracking FAANG · 15:40 · 47K views
Basic Calculator II | Live Coding with Explanation | Leetcode #227Algorithms Made Easy · 7:54 · 28K views
Basic Calculator II | Leetcode 227Pepcoding · 28:18 · 15K views
Basic Calculator II 🔥| Leetcode 227 | Brute + Optimal | Stack | StringAyushi Sharma · 21:02 · 14K views
Basic Calculator II | Leet code 227 | Theory explained + Python codeSai Anish Malla · 19:27 · 14K views
Basic Calculator 2 || Leetcode 227 || Variant Question Big Tech Actually AsksCoding with Minmer · 32:49 · 11K views
227. Basic Calculator II , Top Interview DSA Questions, Java Solution with time complexityShrayansh Jain · 16:11 · 6K views
[Java] Leetcode 227. Basic Calculator II [Stack & Queue #8]Eric Programming · 9:02 · 5K views
LeetCode 227. Basic Calculator IIHappy Coding · 25:18 · 2K views
Basic Calculator II | Expression Evaluation Using Stack | O(n) Optimized Approach | Java Python C++RisingBrain · 27:33 · 2K views
The problem
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 be in the range of [-231, 231 - 1].
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Input: s = "3+2*2" Output: 7
Example 2:
Input: s = " 3/2 " Output: 1
Example 3:
Input: s = " 3+5 / 2 " Output: 5
Constraints:
1 <= s.length <= 3 * 105sconsists of integers and operators('+', '-', '*', '/')separated by some number of spaces.srepresents 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.
Approach overview
Problem Overview: You receive a string representing a mathematical expression containing non‑negative integers and the operators +, -, *, and /. Spaces may appear anywhere. The goal is to evaluate the expression while respecting normal operator precedence (multiplication and division before addition and subtraction).
Approach 1: Use a Stack to Handle Precedence (O(n) time, O(n) space)
This approach scans the string once while building numbers and applying operations as they appear. Keep a stack of intermediate values and track the previous operator. When you finish reading a number, decide what to do based on the last operator: push the number for +, push its negative for -, or pop the top element and immediately compute multiplication or division for * and /. Multiplication and division are resolved immediately, which naturally preserves precedence.
After processing the entire string, sum the values in the stack to produce the final result. Each character is processed once, and each stack operation is constant time. This method is straightforward and mirrors how expression evaluation works conceptually, making it common in stack-based parsing problems involving string expressions.
Approach 2: Two-Pass Parsing Using Sign Tracking (O(n) time, O(1) space)
This approach removes the explicit stack and instead tracks the last computed term. Iterate through the string while building the current number and remembering the previous operator. Maintain two variables: result for the accumulated sum and lastTerm for the most recent value that may still be affected by multiplication or division.
When encountering + or -, add lastTerm to result and start a new term with the current number (positive or negative). For * and /, update lastTerm directly by multiplying or dividing it with the current number. This delays addition until the correct precedence is guaranteed. The algorithm still scans the expression once, but it stores only a few integers, achieving constant auxiliary space.
This technique relies on careful state tracking rather than a container, making it slightly more optimized for memory. It still requires parsing integers from the string and handling truncating division according to problem rules. Problems combining arithmetic evaluation with math parsing often use this pattern.
Recommended for interviews: The stack-based approach is the most widely expected answer because it clearly demonstrates how you enforce operator precedence during a single pass. After presenting that solution, mentioning the constant-space sign-tracking optimization shows deeper understanding of expression parsing and algorithmic refinement.
Approach 1: Approach 1: Use a Stack to Handle Precedence
This approach uses a stack to store numbers and consider operator precedence. Multiplication and division are processed immediately, whereas addition and subtraction modify how numbers are pushed onto the stack.
class BasicCalculatorII:
def calculate(self, s: str) -> int:
stack = []
num = 0
sign = '+'
for i, char in enumerate(s):
if char.isdigit():
num = num * 10 + int(char)
if char in '+-*/' or i == len(s) - 1:
if sign == '+':
stack.append(num)
elif sign == '-':
stack.append(-num)
elif sign == '*':
stack[-1] *= num
elif sign == '/':
stack[-1] = int(stack[-1] / num) # use int() to truncate toward zero in Python
num = 0
sign = char
return sum(stack)
calculator = BasicCalculatorII()
print("Output:", calculator.calculate("3+2*2"))import java.util.Stack;
public class BasicCalculatorII {
public static int calculate(String s) {
Stack<Integer> stack = new Stack<>();
char sign = '+';
int num = 0;
for (int i = 0; i < s.length(); i++) {
if (Character.isDigit(s.charAt(i))) {
num = num * 10 + (s.charAt(i) - '0');
}
if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == s.length() - 1) {
if (sign == '+') {
stack.push(num);
} else if (sign == '-') {
stack.push(-num);
} else if (sign == '*') {
stack.push(stack.pop() * num);
} else if (sign == '/') {
stack.push(stack.pop() / num);
}
sign = s.charAt(i);
num = 0;
}
}
int result = 0;
while (!stack.isEmpty()) {
result += stack.pop();
}
return result;
}
public static void main(String[] args) {
System.out.println("Output: " + calculate("3+2*2"));
}
}#include <iostream>
#include <stack>
int calculate(std::string s) {
std::stack<int> stack;
char sign = '+';
int num = 0;
for (size_t i = 0; i < s.length(); ++i) {
if (isdigit(s[i])) {
num = num * 10 + (s[i] - '0');
}
if (!isdigit(s[i]) && !isspace(s[i]) || i == s.length() - 1) {
if (sign == '+') {
stack.push(num);
} else if (sign == '-') {
stack.push(-num);
} else if (sign == '*') {
int top = stack.top();
stack.pop();
stack.push(top * num);
} else if (sign == '/') {
int top = stack.top();
stack.pop();
stack.push(top / num);
}
sign = s[i];
num = 0;
}
}
int result = 0;
while (!stack.empty()) {
result += stack.top();
stack.pop();
}
return result;
}
int main() {
std::string expression = "3+2*2";
std::cout << "Output: " << calculate(expression) << std::endl;
return 0;
}function calculate(s) {
let stack = [];
let num = 0;
let sign = '+';
for (let i = 0; i < s.length; i++) {
if (!isNaN(s[i]) && s[i] !== ' ') {
num = num * 10 + parseInt(s[i]);
}
if (isNaN(s[i]) && s[i] !== ' ' || i === s.length - 1) {
if (sign === '+') {
stack.push(num);
} else if (sign === '-') {
stack.push(-num);
} else if (sign === '*') {
stack.push(stack.pop() * num);
} else if (sign === '/') {
stack.push(Math.trunc(stack.pop() / num));
}
sign = s[i];
num = 0;
}
}
return stack.reduce((a, b) => a + b);
}
console.log('Output:', calculate('3+2*2'));#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
int calculate(char *s) {
int length = strlen(s);
int stack[length];
int top = -1;
char sign = '+';
int num = 0;
for (int i = 0; i < length; i++) {
if (isdigit(s[i])) {
num = num * 10 + (s[i] - '0');
}
if ((!isdigit(s[i]) && !isspace(s[i])) || i == length - 1) {
if (sign == '+') {
stack[++top] = num;
} else if (sign == '-') {
stack[++top] = -num;
} else if (sign == '*') {
stack[top] *= num;
} else if (sign == '/') {
stack[top] /= num;
}
sign = s[i];
num = 0;
}
}
int result = 0;
while (top != -1) {
result += stack[top--];
}
return result;
}
int main() {
char expression[] = "3+2*2";
printf("Output: %d\n", calculate(expression));
return 0;
}using System;
using System.Collections.Generic;
public class BasicCalculatorII {
public int Calculate(string s) {
Stack<int> stack = new Stack<int>();
char sign = '+';
int num = 0;
for (int i = 0; i < s.Length; i++) {
char c = s[i];
if (Char.IsDigit(c)) {
num = num * 10 + (c - '0');
}
if (!Char.IsDigit(c) && c != ' ' || i == s.Length - 1) {
if (sign == '+') {
stack.Push(num);
} else if (sign == '-') {
stack.Push(-num);
} else if (sign == '*') {
stack.Push(stack.Pop() * num);
} else if (sign == '/') {
stack.Push(stack.Pop() / num);
}
sign = c;
num = 0;
}
}
int result = 0;
while (stack.Count != 0) {
result += stack.Pop();
}
return result;
}
public static void Main() {
BasicCalculatorII calculator = new BasicCalculatorII();
Console.WriteLine("Output: " + calculator.Calculate("3+2*2"));
}
}This Python solution processes the string to calculate values, storing results in a stack. It evaluates '*' and '/' immediately with the stack's last value, pushes '+' and '-' results onto the stack, and finally returns the sum of stack values.
Time Complexity: O(n). Space Complexity: O(n) for the stack.
Approach 2: Approach 2: Two-Pass Parsing Using Sign Tracking
This approach parses the expression twice, first to handle multiplications and divisions, then to process additions and subtractions. This avoids using a stack and simplifies sign handling.
def calculate(s: str) -> int:
num, last_num, result = 0, 0, 0
sign = '+'
for i, char in enumerate(s):
if char.isdigit():
num = num * 10 + int(char)
if not char.isdigit() and char != ' ' or i == len(s) - 1:
if sign == '+':
result += last_num
last_num = num
elif sign == '-':
result += last_num
last_num = -num
elif sign == '*':
last_num *= num
elif sign == '/':
last_num = int(last_num / num) # int() to achieve truncation
num = 0
sign = char
result += last_num
return result
print("Output:", calculate("3+2*2"))public class BasicCalculator {
public static int calculate(String s) {
int num = 0, lastNum = 0, result = 0;
char sign = '+';
int length = s.length();
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
}
if (!Character.isDigit(c) && c != ' ' || i == length - 1) {
if (sign == '+') {
result += lastNum;
lastNum = num;
} else if (sign == '-') {
result += lastNum;
lastNum = -num;
} else if (sign == '*') {
lastNum = lastNum * num;
} else if (sign == '/') {
lastNum = lastNum / num;
}
sign = c;
num = 0;
}
}
result += lastNum;
return result;
}
public static void main(String[] args) {
System.out.println("Output: " + calculate("3+2*2"));
}
}#include <iostream>
int calculate(std::string s) {
int num = 0, lastNum = 0, result = 0;
char sign = '+';
size_t length = s.size();
for (size_t i = 0; i < length; ++i) {
if (isdigit(s[i])) {
num = num * 10 + (s[i] - '0');
}
if (!isdigit(s[i]) && !isspace(s[i]) || i == length - 1) {
if (sign == '+') {
result += lastNum;
lastNum = num;
} else if (sign == '-') {
result += lastNum;
lastNum = -num;
} else if (sign == '*') {
lastNum *= num;
} else if (sign == '/') {
lastNum /= num;
}
sign = s[i];
num = 0;
}
}
result += lastNum;
return result;
}
int main() {
std::string expression = "3+2*2";
std::cout << "Output: " << calculate(expression) << std::endl;
return 0;
}function calculate(s) {
let num = 0, lastNum = 0, result = 0;
let sign = '+';
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (!isNaN(char) && char !== ' ') {
num = num * 10 + parseInt(char);
}
if (isNaN(char) && char !== ' ' || i === s.length - 1) {
if (sign === '+') {
result += lastNum;
lastNum = num;
} else if (sign === '-') {
result += lastNum;
lastNum = -num;
} else if (sign === '*') {
lastNum *= num;
} else if (sign === '/') {
lastNum = Math.trunc(lastNum / num);
}
sign = char;
num = 0;
}
}
result += lastNum;
return result;
}
console.log('Output:', calculate('3+2*2'));#include <stdio.h>
#include <string.h>
#include <ctype.h>
int calculate(char * s) {
int num = 0, n = strlen(s), index = 0;
int lastNum = 0, result = 0;
char sign = '+';
while (index < n) {
char c = s[index];
if (isdigit(c)) {
num = num * 10 + (c - '0');
}
if ((!isdigit(c) && c != ' ') || index == n - 1) {
if (sign == '+') {
result += lastNum;
lastNum = num;
} else if (sign == '-') {
result += lastNum;
lastNum = -num;
} else if (sign == '*') {
lastNum = lastNum * num;
} else if (sign == '/') {
lastNum = lastNum / num;
}
sign = s[index];
num = 0;
}
index++;
}
result += lastNum;
return result;
}
int main() {
char expression[] = "3+2*2";
printf("Output: %d\n", calculate(expression));
return 0;
}public class BasicCalculator {
public int Calculate(string s) {
int num = 0, lastNum = 0, result = 0;
char sign = '+';
int length = s.Length;
for (int i = 0; i < length; i++) {
char c = s[i];
if (Char.IsDigit(c)) {
num = num * 10 + (c - '0');
}
if (!Char.IsDigit(c) && c != ' ' || i == length - 1) {
if (sign == '+') {
result += lastNum;
lastNum = num;
} else if (sign == '-') {
result += lastNum;
lastNum = -num;
} else if (sign == '*') {
lastNum *= num;
} else if (sign == '/') {
lastNum /= num;
}
sign = c;
num = 0;
}
}
result += lastNum;
return result;
}
public static void Main() {
BasicCalculator calculator = new BasicCalculator();
Console.WriteLine("Output: " + calculator.Calculate("3+2*2"));
}
}This Python solution optimizes by evaluating expressions in a single pass without extra space. It handles all calculations inline and tracks only current numbers, last result, and accumulates totals.
Time Complexity: O(n), Space Complexity: O(1) due to parsin without extra space for computation except variables.
Approach 3: Stack
We traverse the string s, and use a variable sign to record the operator before each number. For the first number, its previous operator is considered as a plus sign. Each time we traverse to the end of a number, we decide the calculation method based on sign:
- Plus sign: push the number into the stack;
- Minus sign: push the opposite number into the stack;
- Multiplication and division signs: calculate the number with the top element of the stack, and replace the top element of the stack with the calculation result.
After the traversal ends, the sum of the elements in the stack is the answer.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the string s.
func calculate(s string) int {
sign := '+'
stk := []int{}
v := 0
for i, c := range s {
digit := '0' <= c && c <= '9'
if digit {
v = v*10 + int(c-'0')
}
if i == len(s)-1 || !digit && c != ' ' {
switch sign {
case '+':
stk = append(stk, v)
case '-':
stk = append(stk, -v)
case '*':
stk[len(stk)-1] *= v
case '/':
stk[len(stk)-1] /= v
}
sign = c
v = 0
}
}
ans := 0
for _, v := range stk {
ans += v
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Use a Stack to Handle Precedence | Time Complexity: O(n). Space Complexity: O(n) for the stack. |
| Approach 2: Two-Pass Parsing Using Sign Tracking | Time Complexity: O(n), Space Complexity: O(1) due to parsin without extra space for computation except variables. |
| Stack | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack to Handle Precedence | O(n) | O(n) | General case; easiest to reason about when evaluating expressions with operator precedence. |
| Two-Pass Parsing with Sign Tracking | O(n) | O(1) | When optimizing memory or demonstrating deeper understanding of expression parsing. |
Frequently asked questions
Is Basic Calculator II easy or hard?
Basic Calculator II is considered a medium difficulty problem. The challenge is not the arithmetic itself but correctly handling operator precedence while parsing a string. Once you understand the stack pattern for expression evaluation, the implementation becomes straightforward.
Basic Calculator II Python/Java solution
Python and Java implementations both follow the same logic: iterate through the string, build numbers, track the previous operator, and apply stack operations when an operator or end of string appears. Python typically uses a list as the stack, while Java uses a Stack or ArrayDeque.
How to solve Basic Calculator II in O(n)?
Scan the string once while building numbers and tracking the previous operator. Use a stack or a lastTerm variable to immediately evaluate multiplication and division, while delaying addition and subtraction until the end. Each character is processed once and each arithmetic operation is constant time, resulting in O(n) complexity.
What is the best approach for Basic Calculator II?
The most common approach uses a stack to enforce operator precedence while scanning the expression once. Numbers are pushed for addition and subtraction, while multiplication and division immediately update the top stack value. This keeps the evaluation correct without needing full expression parsing. The algorithm runs in O(n) time and O(n) space.
Is Basic Calculator II asked at Google/Amazon/Meta?
Expression evaluation problems like Basic Calculator II appear in interviews at companies such as Amazon, Google, and Meta because they test string parsing, operator precedence handling, and careful state management. Variations of calculator problems are common in backend and systems interviews.
What data structure is used in Basic Calculator II?
A stack is the primary data structure used in the common solution. It stores intermediate values so multiplication and division can be applied immediately while addition and subtraction are deferred. Some optimized solutions replace the stack with variables that track the last evaluated term.
What is the time complexity of Basic Calculator II?
Basic Calculator II can be solved in O(n) time where n is the length of the string. The algorithm scans the expression once, builds numbers, and performs constant-time operations for each operator. Both the stack approach and the optimized sign-tracking method achieve linear time complexity.