15% off all plans & roadmaps Use code
See plansBasic Calculator II
- LeetCode 227
- Medium
- Stack Patterns
- Expression Evaluation (RPN/Infix)
Updated
TL;DR: Evaluate an expression of non-negative integers using `+`, `-`, `*` and `/` with normal precedence, and without `eval`. Keep a stack of signed terms, fold each `*` or `/` into the term before it, and sum the stack at the end.
Problem
Given a string s which represents an expression, evaluate it and return its value.
The integer division should truncate toward zero.
You may assume the expression is always valid. Every intermediate result stays in the range [-2^31, 2^31 - 1].
Note: You may not use any built-in function that evaluates a string as a mathematical expression, 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 * 10^5sconsists of integers and the operators+,-,*,/, separated by some spaces.srepresents a valid expression.- Every integer in the expression is non-negative and lies in the range
[0, 2^31 - 1]. - The answer fits in a 32-bit integer.
Constraints that matter
scan be 3 * 10^5 characters long, so an O(n^2) approach that rescans the string for each operator is too slow in the worst case.- Operands are non-negative, but intermediate terms can be negative after a subtraction. Division must truncate toward zero, so a negative dividend needs care.
- Every intermediate result fits in 32 bits, so you do not need big integers. Python integers are unbounded anyway, but Java, C++, and C# must not overflow on the way.
- Spaces can appear anywhere between tokens, so the scanner must skip them without treating them as operators.
Hints
Hint 1
The expression mixes two precedence levels and has no parentheses.
Hint 2
Split the string into two lists.
Solution
Intuition
The expression mixes two precedence levels and has no parentheses. That makes it an infix evaluation problem, and the standard tool is a stack. The stack holds the terms that still need to be added. Each term is a signed number that may already have been multiplied or divided.
Picture a pile of index cards, each holding a signed number. The stack is that pile, and the top card is the open term that a * or / can still change. When an operator arrives, you combine the top card with the current number and write the result back on it.
A + or - starts a new term. Later * or / operators can still change that term, so you cannot add it to the total yet. Storing the sign with the number lets you add all the terms at the end.
When you reach * or /, the term before it is still open. Pop that term, combine it with the current number, and push the result back. Each operator does a constant amount of work, so the whole expression takes one pass.
Worked example
Input: s = "12*3-8/2+7*2-5" Output: 41 Explanation: The two multiplications and the division bind first. 12 * 3 = 36, 8 / 2 = 4, and 7 * 2 = 14. The remaining expression is 36 - 4 + 14 - 5, which equals 41. Division is exact here, so truncation does not change the result.
Approach 1: Brute force
Split the string into two lists. nums holds every number, and ops holds every operator between them. Then apply precedence the blunt way: find the first * or /, combine its two neighbours, delete the operator and one number, and start the scan again from the front.
When no multiplicative operator is left, only + and - remain. Walk those from left to right and add or subtract each number.
Steps
- Walk
sonce. On each digit run, build the number. On each operator, append the number tonumsand the operator toops. - Append the final number to
nums. Nowlen(nums)islen(ops) + 1. - While
opscontains*or/, scan from index 0 to find the first one, at index i. - Replace
nums[i]withnums[i] op nums[i + 1], truncating toward zero for division. Deletenums[i + 1]andops[i]. - When no
*or/remains, start the result atnums[0]. - Walk
opsfrom left to right. Addnums[i + 1]for+and subtract it for-. Return the result.
Dry run
Start with nums = [12, 3, 8, 2, 7, 2, 5] and ops = ['*', '-', '/', '+', '*', '-'].
- The first
*is at index 0.12 * 3 = 36. Nownums = [36, 8, 2, 7, 2, 5]andops = ['-', '/', '+', '*', '-']. - The first
*or/is at index 1, the/.8 / 2 = 4. Nownums = [36, 4, 7, 2, 5]andops = ['-', '+', '*', '-']. - The first
*is at index 2.7 * 2 = 14. Nownums = [36, 4, 14, 5]andops = ['-', '+', '-']. - No
*or/is left. Sum from the left:36 - 4 = 32, then32 + 14 = 46, then46 - 5 = 41. Return 41.
Complexity
| Time | O(n^2) |
|---|---|
| Space | O(n) |
Let n be the length of s. The operator count k is at most n. Each collapse scans up to k operators and deletes from two lists, and each deletion shifts up to k items, so one collapse costs O(k). When most operators are * or /, there are about k collapses, so the total work is O(k^2), which is O(n^2). The two lists hold O(n) items in total, so the space is O(n).
PythonTested in our runner
class Solution:
def calculate(self, s: str) -> int:
nums, ops = [], []
num = 0
for ch in s:
if ch.isdigit():
num = num * 10 + int(ch)
elif ch in '+-*/':
nums.append(num)
ops.append(ch)
num = 0
nums.append(num)
def trunc_div(a, b):
q = abs(a) // abs(b)
return q if (a < 0) == (b < 0) else -q
# Collapse every * and / by rescanning from the start
while '*' in ops or '/' in ops:
i = 0
while ops[i] not in ('*', '/'):
i += 1
if ops[i] == '*':
nums[i] = nums[i] * nums[i + 1]
else:
nums[i] = trunc_div(nums[i], nums[i + 1])
del nums[i + 1]
del ops[i]
result = nums[0]
for i, op in enumerate(ops):
if op == '+':
result += nums[i + 1]
else:
result -= nums[i + 1]
return resultJavaTested in our runner
class Solution {
public int calculate(String s) {
List<Integer> nums = new ArrayList<>();
List<Character> ops = new ArrayList<>();
int num = 0;
for (char ch : s.toCharArray()) {
if (Character.isDigit(ch)) {
num = num * 10 + (ch - '0');
} else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
nums.add(num);
ops.add(ch);
num = 0;
}
}
nums.add(num);
// Collapse every * and / by rescanning from the start
while (ops.contains('*') || ops.contains('/')) {
int i = 0;
while (ops.get(i) != '*' && ops.get(i) != '/') {
i++;
}
int a = nums.get(i);
int b = nums.get(i + 1);
// Java integer division already truncates toward zero
int r = (ops.get(i) == '*') ? a * b : a / b;
nums.set(i, r);
nums.remove(i + 1);
ops.remove(i);
}
int result = nums.get(0);
for (int i = 0; i < ops.size(); i++) {
if (ops.get(i) == '+') {
result += nums.get(i + 1);
} else {
result -= nums.get(i + 1);
}
}
return result;
}
}C++Tested in our runner
using namespace std;
class Solution {
public:
int calculate(string s) {
vector<int> nums;
vector<char> ops;
int num = 0;
for (char ch : s) {
if (ch >= '0' && ch <= '9') {
num = num * 10 + (ch - '0');
} else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
nums.push_back(num);
ops.push_back(ch);
num = 0;
}
}
nums.push_back(num);
// Collapse every * and / by rescanning from the start
auto hasMulDiv = [&]() {
for (char c : ops) {
if (c == '*' || c == '/') return true;
}
return false;
};
while (hasMulDiv()) {
int i = 0;
while (ops[i] != '*' && ops[i] != '/') {
i++;
}
int a = nums[i];
int b = nums[i + 1];
// C++11 and later truncate integer division toward zero
nums[i] = (ops[i] == '*') ? a * b : a / b;
nums.erase(nums.begin() + i + 1);
ops.erase(ops.begin() + i);
}
int result = nums[0];
for (int i = 0; i < (int)ops.size(); i++) {
if (ops[i] == '+') {
result += nums[i + 1];
} else {
result -= nums[i + 1];
}
}
return result;
}
};JavaScriptTested in our runner
var calculate = function(s) {
const nums = [];
const ops = [];
let num = 0;
for (const ch of s) {
if (ch >= '0' && ch <= '9') {
num = num * 10 + (ch.charCodeAt(0) - 48);
} else if ('+-*/'.includes(ch)) {
nums.push(num);
ops.push(ch);
num = 0;
}
}
nums.push(num);
// Collapse every * and / by rescanning from the start
while (ops.includes('*') || ops.includes('/')) {
let i = 0;
while (ops[i] !== '*' && ops[i] !== '/') {
i++;
}
const a = nums[i];
const b = nums[i + 1];
// Math.trunc truncates toward zero
nums[i] = ops[i] === '*' ? a * b : Math.trunc(a / b);
nums.splice(i + 1, 1);
ops.splice(i, 1);
}
let result = nums[0];
for (let i = 0; i < ops.length; i++) {
if (ops[i] === '+') {
result += nums[i + 1];
} else {
result -= nums[i + 1];
}
}
return result;
};GoTested in our runner
func calculate(s string) int {
nums := []int{}
ops := []byte{}
num := 0
for i := 0; i < len(s); i++ {
ch := s[i]
if ch >= '0' && ch <= '9' {
num = num*10 + int(ch-'0')
} else if ch == '+' || ch == '-' || ch == '*' || ch == '/' {
nums = append(nums, num)
ops = append(ops, ch)
num = 0
}
}
nums = append(nums, num)
// Collapse every * and / by rescanning from the start
for {
idx := -1
for i, op := range ops {
if op == '*' || op == '/' {
idx = i
break
}
}
if idx == -1 {
break
}
a, b := nums[idx], nums[idx+1]
if ops[idx] == '*' {
nums[idx] = a * b
} else {
nums[idx] = a / b // Go truncates toward zero
}
nums = append(nums[:idx+1], nums[idx+2:]...)
ops = append(ops[:idx], ops[idx+1:]...)
}
result := nums[0]
for i, op := range ops {
if op == '+' {
result += nums[i+1]
} else {
result -= nums[i+1]
}
}
return result
}C#Tested in our runner
public class Solution {
public int calculate(string s) {
var nums = new List<int>();
var ops = new List<char>();
int num = 0;
foreach (char ch in s) {
if (char.IsDigit(ch)) {
num = num * 10 + (ch - '0');
} else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
nums.Add(num);
ops.Add(ch);
num = 0;
}
}
nums.Add(num);
// Collapse every * and / by rescanning from the start
while (ops.Contains('*') || ops.Contains('/')) {
int i = 0;
while (ops[i] != '*' && ops[i] != '/') {
i++;
}
int a = nums[i];
int b = nums[i + 1];
// C# integer division truncates toward zero
nums[i] = ops[i] == '*' ? a * b : a / b;
nums.RemoveAt(i + 1);
ops.RemoveAt(i);
}
int result = nums[0];
for (int i = 0; i < ops.Count; i++) {
if (ops[i] == '+') {
result += nums[i + 1];
} else {
result -= nums[i + 1];
}
}
return result;
}
}The Expression Evaluation (RPN/Infix) infographic is part of Pro
A one-page visual of the pattern: when it applies, the steps and the invariant to keep.
Unlock the infographicSolution pattern
Expression Evaluation (RPN/Infix)
Part of Stack Patterns
Approach 2: One-pass stackOptimalExpression Evaluation (RPN/Infix)
What is slow in the brute force: each collapse rescans from index 0 to find the next * or /, and each deletion shifts every later element. With k operators, that is up to k collapses at O(k) each, so the total is O(n^2) on inputs such as 1*1*1*....
The insight that fixes it: a * or / only needs the term right before it. Keep the terms on a stack. When you read an operator, apply the pending operator to the number you finished, which means you rewrite the top of the stack in place. One left-to-right pass is enough.
Why it is correct. At every point, the stack holds the finished terms, and only the top term can still be changed by a * or /. Precedence means a * or / binds to the number right before it, so earlier terms are final. Summing the stack therefore gives the value of the whole expression, because each term already carries its sign.
Steps
- Set
num = 0, an empty stack, andop = '+', the operator that comes before the current number. - For each character, if it is a digit, set
num = num * 10 + digit. Skip spaces. - When the character is
+,-,*,/, or the last index, applyoptonum.+pushesnum,-pushes-num,*pops and multiplies, and/pops and divides with truncation. - Set
opto the current character and resetnum = 0. - After the loop, add every value on the stack and return the sum.
Dry run
Walk through s = "12*3-8/2+7*2-5". Each row is one operator or the last character. The num column shows the number read so far, and the stack shows the terms after the action.
| Read | Action | num | op | stack |
|---|---|---|---|---|
1, 2 | build the number | 12 | + | [] |
* | apply + to 12, push 12 | 0 | * | [12] |
3 | build the number | 3 | * | [12] |
- | apply * to 3, pop 12, push 36 | 0 | - | [36] |
8 | build the number | 8 | - | [36] |
/ | apply - to 8, push -8 | 0 | / | [36, -8] |
2 | build the number | 2 | / | [36, -8] |
+ | apply / to 2, pop -8, push -4 | 0 | + | [36, -4] |
7 | build the number | 7 | + | [36, -4] |
* | apply + to 7, push 7 | 0 | * | [36, -4, 7] |
2 | build the number | 2 | * | [36, -4, 7] |
- | apply * to 2, pop 7, push 14 | 0 | - | [36, -4, 14] |
5 | build the number | 5 | - | [36, -4, 14] |
last 5 | apply - to 5, push -5 | 0 | 5 | [36, -4, 14, -5] |
The stack holds [36, -4, 14, -5]. Summing gives 36 - 4 + 14 - 5 = 41. Return 41.
Complexity
| Time | O(n) |
|---|---|
| Space | O(n) |
Let n be the length of s. The loop visits each character once. A digit does constant work, and an operator does one push or one pop followed by one push, so time is O(n). Each number adds at most one stack entry, so the stack never holds more than O(n) items, which is the space bound. On 1+2+3+..., the stack grows to about n/2 entries.
PythonTested in our runner
class Solution:
def calculate(self, s: str) -> int:
stack = []
num = 0
op = '+' # operator that comes before the current number
n = len(s)
for i, ch in enumerate(s):
if ch.isdigit():
num = num * 10 + int(ch)
if ch in '+-*/' or i == n - 1:
# Apply the pending operator to the number we just finished
if op == '+':
stack.append(num)
elif op == '-':
stack.append(-num)
elif op == '*':
stack.append(stack.pop() * num)
else:
top = stack.pop()
q = abs(top) // abs(num) # divide magnitudes, then restore the sign
stack.append(q if (top < 0) == (num < 0) else -q)
op = ch
num = 0
return sum(stack)JavaTested in our runner
class Solution {
public int calculate(String s) {
Deque<Integer> terms = new ArrayDeque<>();
int num = 0;
char op = '+'; // operator that comes before the current number
int n = s.length();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
num = num * 10 + (ch - '0');
}
if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || i == n - 1) {
if (op == '+') {
terms.push(num);
} else if (op == '-') {
terms.push(-num);
} else if (op == '*') {
terms.push(terms.pop() * num);
} else {
terms.push(terms.pop() / num); // truncates toward zero
}
op = ch;
num = 0;
}
}
int result = 0;
for (int v : terms) {
result += v;
}
return result;
}
}C++Tested in our runner
using namespace std;
class Solution {
public:
int calculate(string s) {
vector<int> terms;
int num = 0;
char op = '+'; // operator that comes before the current number
int n = s.size();
for (int i = 0; i < n; i++) {
char ch = s[i];
if (ch >= '0' && ch <= '9') {
num = num * 10 + (ch - '0');
}
if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || i == n - 1) {
if (op == '+') {
terms.push_back(num);
} else if (op == '-') {
terms.push_back(-num);
} else if (op == '*') {
int top = terms.back();
terms.pop_back();
terms.push_back(top * num);
} else {
int top = terms.back();
terms.pop_back();
terms.push_back(top / num); // truncates toward zero
}
op = ch;
num = 0;
}
}
int result = 0;
for (int v : terms) {
result += v;
}
return result;
}
};JavaScriptTested in our runner
var calculate = function(s) {
const terms = [];
let num = 0;
let op = '+'; // operator that comes before the current number
const n = s.length;
for (let i = 0; i < n; i++) {
const ch = s[i];
if (ch >= '0' && ch <= '9') {
num = num * 10 + (ch.charCodeAt(0) - 48);
}
if (ch === '+' || ch === '-' || ch === '*' || ch === '/' || i === n - 1) {
if (op === '+') {
terms.push(num);
} else if (op === '-') {
terms.push(-num);
} else if (op === '*') {
terms.push(terms.pop() * num);
} else {
terms.push(Math.trunc(terms.pop() / num));
}
op = ch;
num = 0;
}
}
return terms.reduce((a, b) => a + b, 0);
};GoTested in our runner
func calculate(s string) int {
terms := []int{}
num := 0
var op byte = '+' // operator that comes before the current number
n := len(s)
for i := 0; i < n; i++ {
ch := s[i]
if ch >= '0' && ch <= '9' {
num = num*10 + int(ch-'0')
}
if ch == '+' || ch == '-' || ch == '*' || ch == '/' || i == n-1 {
switch op {
case '+':
terms = append(terms, num)
case '-':
terms = append(terms, -num)
case '*':
top := terms[len(terms)-1]
terms = terms[:len(terms)-1]
terms = append(terms, top*num)
default:
top := terms[len(terms)-1]
terms = terms[:len(terms)-1]
terms = append(terms, top/num) // truncates toward zero
}
op = ch
num = 0
}
}
result := 0
for _, v := range terms {
result += v
}
return result
}C#Tested in our runner
public class Solution {
public int calculate(string s) {
var terms = new List<int>();
int num = 0;
char op = '+'; // operator that comes before the current number
int n = s.Length;
for (int i = 0; i < n; i++) {
char ch = s[i];
if (char.IsDigit(ch)) {
num = num * 10 + (ch - '0');
}
if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || i == n - 1) {
if (op == '+') {
terms.Add(num);
} else if (op == '-') {
terms.Add(-num);
} else if (op == '*') {
int top = terms[terms.Count - 1];
terms.RemoveAt(terms.Count - 1);
terms.Add(top * num);
} else {
int top = terms[terms.Count - 1];
terms.RemoveAt(terms.Count - 1);
terms.Add(top / num); // truncates toward zero
}
op = ch;
num = 0;
}
}
int result = 0;
foreach (int v in terms) {
result += v;
}
return result;
}
}Common mistakes
result += numfor-instead of pushing-num. The sign is lost, and a later*or/cannot see it. Push the negated number so the stack holds signed terms.op = chplaced before the flush block. The pending operator is then applied with the wrong symbol. Updateoponly after the flush has used the old value.- Missing final flush: the check is only
if ch in '+-*/', so the last number is never pushed. Addor i == n - 1to the condition. - Resetting
numon every digit, or pushing on every digit.42must becomenum = num * 10 + digiton each digit, so the number is built once at the next operator. - Python
//orint(top / num)on negative values.-7 // 2is -4, and the problem wants -3. Divide the absolute values and restore the sign. - Treating a space as an operator. A space can flush the number and set
opto a character that matches no branch. Skip spaces, and flush only on+ - * /or at the last index.
Edge cases
0: a single number. The final flush at the last index pushes 0, and the answer is 0.7: a single digit at the last index. Without thei == n - 1check, the answer would be 0.3/2: leading and trailing spaces are skipped, and the answer is 1 because truncation rounds 1.5 toward zero.1-7/2: a division of a negative term. The stack holds -7 before/, and truncation gives -3. The answer is 1 - 3 = -2. Floor division would give -3 instead.14-3/2: multi-digit operands with precedence on the right. The answer is 14 - 1 = 13.0-2147483647: the largest magnitude term, negated. The answer is -2147483647, which fits in 32 bits.
Follow-ups interviewers ask
- Can you solve it in O(1) extra space?
- Yes. Keep two variables,
totalandlast, wherelastis the open term. On+or-, addlasttototal, then setlastto the new signed number. On*or/, updatelastin place. At the end, returntotal + last. - How would you handle parentheses?
- Parentheses need saved state. On
(, push the running total and the pending sign, then start a fresh total. On), finish the inner total, pop the saved sign and total, and combine them. The expression on this page has no parentheses, so the stack of terms is enough. - What if the expression does not fit in memory?
- Read it as a stream. The O(1) variant needs only the numbers
total,last, and the current number, plus the pending operator. Each character is read once, so the input can come from a file or socket one character at a time.
Basic Calculator II FAQ
What is the time complexity of Basic Calculator II?
The one-pass stack solution runs in O(n) time, where n is the length of s. Each character is read once and does constant work. The brute force that rescans for * and / runs in O(n^2).
Why use a stack for Basic Calculator II?
A stack holds the terms that are waiting to be added. A * or / only needs the term right before it, which is the top of the stack. That lets precedence work in a single left-to-right pass.
Can Basic Calculator II be solved in O(1) extra space?
Yes. Keep a running total and the most recent open term in two variables. The stack is not needed, because only the last term ever changes.
Why does integer division need care in Python for Basic Calculator II?
Python's // rounds toward negative infinity, so -7 // 2 is -4. The problem needs truncation toward zero, which gives -3. Divide the absolute values, then restore the sign.
Is eval allowed for Basic Calculator II?
No. The problem forbids built-in evaluators such as eval(). The stack approach reads the digits and operators directly, so no string evaluator is needed.
Asked at
See which companies ask this — Pro
Related problems
- Evaluate Reverse Polish Notation · same technique: Expression Evaluation (RPN/Infix)
- Basic Calculator · same technique: Expression Evaluation (RPN/Infix)
- Basic Calculator III · same technique: Expression Evaluation (RPN/Infix)
- Min Stack · same pattern: Stack Patterns
- Daily Temperatures · same pattern: Stack Patterns
- Car Fleet · same pattern: Stack Patterns
- Valid Parenthesis String · same pattern: Stack Patterns
- Simplify Path · same pattern: Stack Patterns
- Decode String · same pattern: Stack Patterns
- Asteroid Collision · same pattern: Stack Patterns