Prerequisites
Before attempting this problem, you should be comfortable with:
- Stack Data Structure - Used to defer lower-precedence operations while computing higher-precedence ones
- String Parsing - Building multi-digit numbers from character sequences and handling whitespace
- Operator Precedence - Understanding that multiplication/division must be evaluated before addition/subtraction
1. Stack
Intuition
The challenge with evaluating expressions is handling operator precedence. Multiplication and division must be done before addition and subtraction. We can use a stack to defer the addition and subtraction while immediately computing multiplication and division. For + and -, we push numbers onto the stack (negative for subtraction). For * and /, we pop the previous number, compute the result, and push it back. At the end, summing the stack gives us the answer.
Algorithm
- Remove all spaces from the string and initialize an empty
stack.
- Track the current
num and the previous op (start with +).
- For each character:
- If it's a digit, build up the current
num.
- If it's an operator or the last character:
- Apply the previous
op: push for +, push negative for -, multiply top for *, divide top for /.
- Reset the current
num and update the previous op.
- Return the sum of all elements in the
stack.
class Solution:
def calculate(self, s: str) -> int:
stack = []
num = 0
op = '+'
s = s.replace(' ', '')
for i, ch in enumerate(s):
if ch.isdigit():
num = num * 10 + int(ch)
if (not ch.isdigit()) or i == len(s) - 1:
if op == '+':
stack.append(num)
elif op == '-':
stack.append(-num)
elif op == '*':
stack.append(stack.pop() * num)
else:
prev = stack.pop()
stack.append(int(prev / num))
op = ch
num = 0
return sum(stack)
public class Solution {
public int calculate(String s) {
s = s.replace(" ", "");
Stack<Integer> stack = new Stack<>();
int num = 0;
char op = '+';
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
num = num * 10 + (ch - '0');
}
if (!Character.isDigit(ch) || i == s.length() - 1) {
if (op == '+') {
stack.push(num);
} else if (op == '-') {
stack.push(-num);
} else if (op == '*') {
stack.push(stack.pop() * num);
} else {
int prev = stack.pop();
stack.push(prev / num);
}
op = ch;
num = 0;
}
}
int res = 0;
while (!stack.isEmpty()) {
res += stack.pop();
}
return res;
}
}
class Solution {
public:
int calculate(string s) {
s.erase(remove(s.begin(), s.end(), ' '), s.end());
vector<int> stack;
int num = 0;
char op = '+';
for (int i = 0; i < s.size(); i++) {
char ch = s[i];
if (isdigit(ch)) {
num = num * 10 + (ch - '0');
}
if (!isdigit(ch) || i == s.size() - 1) {
if (op == '+') {
stack.push_back(num);
} else if (op == '-') {
stack.push_back(-num);
} else if (op == '*') {
int prev = stack.back(); stack.pop_back();
stack.push_back(prev * num);
} else {
int prev = stack.back(); stack.pop_back();
stack.push_back(prev / num);
}
op = ch;
num = 0;
}
}
int res = 0;
for (int x : stack) res += x;
return res;
}
};
class Solution {
calculate(s) {
s = s.replace(/\s+/g, '');
const stack = [];
let num = 0;
let op = '+';
for (let i = 0; i < s.length; i++) {
const ch = s[i];
if (/\d/.test(ch)) {
num = num * 10 + (ch - '0');
}
if (!/\d/.test(ch) || i === s.length - 1) {
if (op === '+') {
stack.push(num);
} else if (op === '-') {
stack.push(-num);
} else if (op === '*') {
stack.push(stack.pop() * num);
} else {
const prev = stack.pop();
stack.push(Math.trunc(prev / num));
}
op = ch;
num = 0;
}
}
return stack.reduce((a, b) => a + b, 0);
}
}
public class Solution {
public int Calculate(string s) {
s = s.Replace(" ", "");
var stack = new Stack<int>();
int num = 0;
char op = '+';
for (int i = 0; i < s.Length; i++) {
char ch = s[i];
if (char.IsDigit(ch)) {
num = num * 10 + (ch - '0');
}
if (!char.IsDigit(ch) || i == s.Length - 1) {
if (op == '+') {
stack.Push(num);
} else if (op == '-') {
stack.Push(-num);
} else if (op == '*') {
int prev = stack.Pop();
stack.Push(prev * num);
} else {
int prev = stack.Pop();
stack.Push(prev / num);
}
op = ch;
num = 0;
}
}
int res = 0;
while (stack.Count > 0) {
res += stack.Pop();
}
return res;
}
}
func calculate(s string) int {
s = strings.ReplaceAll(s, " ", "")
stack := []int{}
num := 0
op := byte('+')
for i := 0; i < len(s); i++ {
ch := s[i]
if ch >= '0' && ch <= '9' {
num = num*10 + int(ch-'0')
}
if (ch < '0' || ch > '9') || i == len(s)-1 {
switch op {
case '+':
stack = append(stack, num)
case '-':
stack = append(stack, -num)
case '*':
prev := stack[len(stack)-1]
stack = stack[:len(stack)-1]
stack = append(stack, prev*num)
case '/':
prev := stack[len(stack)-1]
stack = stack[:len(stack)-1]
stack = append(stack, prev/num)
}
op = ch
num = 0
}
}
res := 0
for _, v := range stack {
res += v
}
return res
}
class Solution {
fun calculate(s: String): Int {
val str = s.replace(" ", "")
val stack = mutableListOf<Int>()
var num = 0
var op = '+'
for (i in str.indices) {
val ch = str[i]
if (ch.isDigit()) {
num = num * 10 + (ch - '0')
}
if (!ch.isDigit() || i == str.length - 1) {
when (op) {
'+' -> stack.add(num)
'-' -> stack.add(-num)
'*' -> stack.add(stack.removeLast() * num)
'/' -> stack.add(stack.removeLast() / num)
}
op = ch
num = 0
}
}
return stack.sum()
}
}
class Solution {
func calculate(_ s: String) -> Int {
let str = s.filter { $0 != " " }
let chars = Array(str)
var stack = [Int]()
var num = 0
var op: Character = "+"
for i in 0..<chars.count {
let ch = chars[i]
if ch.isNumber {
num = num * 10 + Int(String(ch))!
}
if !ch.isNumber || i == chars.count - 1 {
switch op {
case "+":
stack.append(num)
case "-":
stack.append(-num)
case "*":
stack.append(stack.removeLast() * num)
case "/":
stack.append(stack.removeLast() / num)
default:
break
}
op = ch
num = 0
}
}
return stack.reduce(0, +)
}
}
impl Solution {
pub fn calculate(s: String) -> i32 {
let s: Vec<u8> = s.bytes().filter(|&b| b != b' ').collect();
let mut stack: Vec<i32> = Vec::new();
let mut num: i32 = 0;
let mut op = b'+';
for i in 0..s.len() {
let ch = s[i];
if ch.is_ascii_digit() {
num = num * 10 + (ch - b'0') as i32;
}
if !ch.is_ascii_digit() || i == s.len() - 1 {
match op {
b'+' => stack.push(num),
b'-' => stack.push(-num),
b'*' => {
let prev = stack.pop().unwrap();
stack.push(prev * num);
}
b'/' => {
let prev = stack.pop().unwrap();
stack.push(prev / num);
}
_ => {}
}
op = ch;
num = 0;
}
}
stack.iter().sum()
}
}
Time & Space Complexity
- Time complexity: O(n)
- Space complexity: O(n)
2. Without Stack
Intuition
We can avoid using a stack by realizing that we only need to track two values: the running total of all fully computed terms, and the prev term that might still be involved in a multiplication or division. When we see + or -, we can add the prev term to our total and start a new term. When we see * or /, we update the prev term directly. This reduces space complexity to O(1).
Algorithm
- Initialize
total, prev, and num to 0, and set the initial operator to +.
- Iterate through the string (plus one extra iteration to process the last number).
- Skip spaces. Build up multi-digit numbers.
- When we hit an operator or the end:
- For
+: add prev to total, set prev to num.
- For
-: add prev to total, set prev to -num.
- For
*: multiply prev by num.
- For
/: divide prev by num (truncate toward zero).
- Update the operator and reset
num.
- Add the final
prev to total and return it.
class Solution:
def calculate(self, s: str) -> int:
total = prev = num = 0
op = '+'
n = len(s)
i = 0
while i <= n:
ch = s[i] if i < n else '+'
if ch == ' ':
i += 1
continue
if '0' <= ch <= '9':
num = num * 10 + (ord(ch) - ord('0'))
else:
if op == '+':
total += prev
prev = num
elif op == '-':
total += prev
prev = -num
elif op == '*':
prev = prev * num
else:
if prev < 0:
prev = -(-prev // num)
else:
prev = prev // num
op = ch
num = 0
i += 1
total += prev
return total
public class Solution {
public int calculate(String s) {
int total = 0, prev = 0, num = 0;
char op = '+';
int n = s.length(), i = 0;
while (i <= n) {
char ch = i < n ? s.charAt(i) : '+';
if (ch == ' ') {
i++;
continue;
}
if (Character.isDigit(ch)) {
num = num * 10 + (ch - '0');
} else {
switch (op) {
case '+':
total += prev;
prev = num;
break;
case '-':
total += prev;
prev = -num;
break;
case '*':
prev = prev * num;
break;
default:
prev = prev / num;
}
op = ch;
num = 0;
}
i++;
}
total += prev;
return total;
}
}
class Solution {
public:
int calculate(string s) {
int total = 0, prev = 0, num = 0;
char op = '+';
int n = s.size(), i = 0;
while (i <= n) {
char ch = i < n ? s[i] : '+';
if (ch == ' ') {
i++;
continue;
}
if (isdigit(ch)) {
num = num * 10 + (ch - '0');
} else {
if (op == '+') {
total += prev;
prev = num;
} else if (op == '-') {
total += prev;
prev = -num;
} else if (op == '*') {
prev = prev * num;
} else {
prev = prev / num;
}
op = ch;
num = 0;
}
i++;
}
total += prev;
return total;
}
};
class Solution {
calculate(s) {
let total = 0,
prev = 0,
num = 0;
let op = '+';
const n = s.length;
let i = 0;
while (i <= n) {
const ch = i < n ? s[i] : '+';
if (ch === ' ') {
i++;
continue;
}
if (ch >= '0' && ch <= '9') {
num = num * 10 + (ch.charCodeAt(0) - 48);
} else {
if (op === '+') {
total += prev;
prev = num;
} else if (op === '-') {
total += prev;
prev = -num;
} else if (op === '*') {
prev = prev * num;
} else {
prev = (prev / num) | 0;
}
op = ch;
num = 0;
}
i++;
}
total += prev;
return total;
}
}
public class Solution {
public int Calculate(string s) {
int total = 0, prev = 0, num = 0;
char op = '+';
int n = s.Length, i = 0;
while (i <= n) {
char ch = i < n ? s[i] : '+';
if (ch == ' ') {
i++;
continue;
}
if (char.IsDigit(ch)) {
num = num * 10 + (ch - '0');
} else {
switch (op) {
case '+':
total += prev;
prev = num;
break;
case '-':
total += prev;
prev = -num;
break;
case '*':
prev = prev * num;
break;
default:
prev = prev / num;
break;
}
op = ch;
num = 0;
}
i++;
}
total += prev;
return total;
}
}
func calculate(s string) int {
total, prev, num := 0, 0, 0
op := byte('+')
n := len(s)
i := 0
for i <= n {
var ch byte
if i < n {
ch = s[i]
} else {
ch = '+'
}
if ch == ' ' {
i++
continue
}
if ch >= '0' && ch <= '9' {
num = num*10 + int(ch-'0')
} else {
switch op {
case '+':
total += prev
prev = num
case '-':
total += prev
prev = -num
case '*':
prev = prev * num
default:
prev = prev / num
}
op = ch
num = 0
}
i++
}
total += prev
return total
}
class Solution {
fun calculate(s: String): Int {
var total = 0
var prev = 0
var num = 0
var op = '+'
val n = s.length
var i = 0
while (i <= n) {
val ch = if (i < n) s[i] else '+'
if (ch == ' ') {
i++
continue
}
if (ch.isDigit()) {
num = num * 10 + (ch - '0')
} else {
when (op) {
'+' -> {
total += prev
prev = num
}
'-' -> {
total += prev
prev = -num
}
'*' -> prev *= num
else -> prev /= num
}
op = ch
num = 0
}
i++
}
total += prev
return total
}
}
class Solution {
func calculate(_ s: String) -> Int {
var total = 0, prev = 0, num = 0
var op: Character = "+"
let chars = Array(s)
let n = chars.count
var i = 0
while i <= n {
let ch: Character = i < n ? chars[i] : "+"
if ch == " " {
i += 1
continue
}
if ch.isNumber {
num = num * 10 + Int(String(ch))!
} else {
switch op {
case "+":
total += prev
prev = num
case "-":
total += prev
prev = -num
case "*":
prev = prev * num
default:
prev = prev / num
}
op = ch
num = 0
}
i += 1
}
total += prev
return total
}
}
impl Solution {
pub fn calculate(s: String) -> i32 {
let s = s.as_bytes();
let n = s.len();
let mut total: i32 = 0;
let mut prev: i32 = 0;
let mut num: i32 = 0;
let mut op = b'+';
let mut i = 0;
while i <= n {
let ch = if i < n { s[i] } else { b'+' };
if ch == b' ' {
i += 1;
continue;
}
if ch.is_ascii_digit() {
num = num * 10 + (ch - b'0') as i32;
} else {
match op {
b'+' => { total += prev; prev = num; }
b'-' => { total += prev; prev = -num; }
b'*' => { prev *= num; }
_ => { prev /= num; }
}
op = ch;
num = 0;
}
i += 1;
}
total += prev;
total
}
}
Time & Space Complexity
- Time complexity: O(n)
- Space complexity: O(1)
Common Pitfalls
Incorrect Integer Division with Negative Numbers
Division in this problem truncates toward zero, but some languages (like Python) use floor division by default, which truncates toward negative infinity. This gives wrong results for negative numbers.
Forgetting to Process the Last Number
The algorithm typically processes a number when it encounters an operator. However, the last number in the expression has no operator after it, so it might never get processed unless you handle this edge case explicitly.
Not Handling Spaces Correctly
The expression can contain spaces between numbers and operators. Failing to skip or remove spaces causes parsing errors or treats spaces as invalid characters.
