Basic Calculator II

Med

#0215Time: O(n) where n is the length of the input string - we need to traverse the string onceSpace: O(n) where n is the length of the input string - in worst case, all numbers could be pushed to stack20 companies

Patterns

Math

Data structures

String Stack

Companies

Accenture Airbnb ByteDance DoorDash

Prompt

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 [-2³¹, 2³¹ - 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 * 10⁵
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, 2³¹ - 1].
The answer is guaranteed to fit in a 32-bit integer.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a stack to evaluate the expression in two passes. In the first pass, we handle multiplication and division operations, and in the second pass, we handle addition and subtraction.

Algorithm

Initialize a stack and variables for lastOperation and currentNumber
Iterate through each character in the string
If character is digit, build the number
If character is operator or last character:
- Process previous operation
- Update lastOperation
After processing all characters, sum up the stack

Walkthrough

The idea is to process the expression in two steps:

First pass: Process multiplication and division operations

Iterate through the string character by character
Keep track of current number and last operation
When encountering an operator or end of string:
- If previous operation was multiplication, multiply with stack top
- If previous operation was division, divide with stack top
- For addition/subtraction, push number to stack

Second pass: Process addition and subtraction

Sum up all numbers in the stack considering their signs

Here's the implementation:

1public int calculate(String s) {2    Stack<Integer> stack = new Stack<>();3    char lastOp = '+';4    int num = 0;5    6    for (int i = 0; i < s.length(); i++) {7        char c = s.charAt(i);8        9        if (Character.isDigit(c)) {10            num = num * 10 + (c - '0');11        }12        13        if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {14            if (lastOp == '+') {15                stack.push(num);16            } else if (lastOp == '-') {17                stack.push(-num);18            } else if (lastOp == '*') {19                stack.push(stack.pop() * num);20            } else if (lastOp == '/') {21                stack.push(stack.pop() / num);22            }23            lastOp = c;24            num = 0;25        }26    }27    28    int result = 0;29    while (!stack.isEmpty()) {30        result += stack.pop();31    }32    return result;33}

Complexity

Time

O(n) where n is the length of the input string - we need to traverse the string once

Space

O(n) where n is the length of the input string - in worst case, all numbers could be pushed to stack

Trade-offs

Pros

Easy to understand and implement
Can handle expressions with spaces
Processes operations in correct order of precedence

Cons

Uses extra space for stack
Makes two passes through the data (one implicit in summing stack)
Not easily extensible for more operators or different precedence rules

This approach processes the expression in a single pass while maintaining only the necessary variables to track the current state and previous values. It doesn't use any additional data structures like a stack.

Algorithm

Initialize variables for result, currentNumber, lastNumber, and operation
Iterate through the string once
Build numbers when digits are encountered
When operator is encountered:
- For +/-, add lastNumber to result and update lastNumber
- For */, perform operation on lastNumber
Return result + lastNumber

Walkthrough

The idea is to keep track of the last calculated number and the current number being processed. We only need to store the previous number when we encounter multiplication or division.

Here's the implementation:

1public int calculate(String s) {2    int length = s.length();3    int currentNumber = 0;4    int lastNumber = 0;5    int result = 0;6    char operation = '+';7    8    for (int i = 0; i < length; i++) {9        char currentChar = s.charAt(i);10        11        if (Character.isDigit(currentChar)) {12            currentNumber = (currentNumber * 10) + (currentChar - '0');13        }14        15        if (!Character.isDigit(currentChar) && !Character.isWhitespace(currentChar) || i == length - 1) {16            if (operation == '+' || operation == '-') {17                result += lastNumber;18                lastNumber = (operation == '+') ? currentNumber : -currentNumber;19            } else if (operation == '*') {20                lastNumber = lastNumber * currentNumber;21            } else if (operation == '/') {22                lastNumber = lastNumber / currentNumber;23            }24            operation = currentChar;25            currentNumber = 0;26        }27    }28    29    result += lastNumber;30    return result;31}

Complexity

Time

O(n) where n is the length of the input string - we only need one pass through the string

Space

O(1) - only uses a constant amount of extra space regardless of input size

Trade-offs

Pros

Single pass through the input
Constant extra space
More efficient than stack-based approach
Handles operator precedence correctly

Cons

Slightly more complex logic
Less intuitive than stack-based approach
Harder to modify for additional operators or different precedence rules

Solutions

Solution

1using System.Collections.Generic ; using System.Linq ; struct Element { public char Op ; public int Number ; public Element ( char op , int number ) { Op = op ; Number = number ; } } public class Solution { public int Calculate ( string s ) { var stack = new Stack < Element >(); var readingNumber = false ; var number = 0 ; var op = '+' ; foreach ( var ch in (( IEnumerable < char >) s ). Concat ( Enumerable . Repeat ( '+' , 1 ))) { if ( ch >= '0' && ch <= '9' ) { if (! readingNumber ) { readingNumber = true ; number = 0 ; } number = ( number * 10 ) + ( ch - '0' ); } else if ( ch != ' ' ) { readingNumber = false ; if ( op == '+' || op == '-' ) { if ( stack . Count == 2 ) { var prev = stack . Pop (); var first = stack . Pop (); if ( prev . Op == '+' ) { stack . Push ( new Element ( first . Op , first . Number + prev . Number )); } else // '-' { stack . Push ( new Element ( first . Op , first . Number - prev . Number )); } } stack . Push ( new Element ( op , number )); } else { var prev = stack . Pop (); if ( op == '*' ) { stack . Push ( new Element ( prev . Op , prev . Number * number )); } else // '/' { stack . Push ( new Element ( prev . Op , prev . Number / number )); } } op = ch ; } } if ( stack . Count == 2 ) { var second = stack . Pop (); var first = stack . Pop (); if ( second . Op == '+' ) { stack . Push ( new Element ( first . Op , first . Number + second . Number )); } else // '-' { stack . Push ( new Element ( first . Op , first . Number - second . Number )); } } return stack . Peek (). Number ; } }

1class Solution { public int calculate ( String s ) { Deque < Integer > stk = new ArrayDeque <>(); char sign = '+' ; int v = 0 ; for ( int i = 0 ; i < s . length (); ++ i ) { char c = s . charAt ( i ); if ( Character . isDigit ( c )) { v = v * 10 + ( c - '0' ); } if ( i == s . length () - 1 || c == '+' || c == '-' || c == '*' || c == '/' ) { if ( sign == '+' ) { stk . push ( v ); } else if ( sign == '-' ) { stk . push (- v ); } else if ( sign == '*' ) { stk . push ( stk . pop () * v ); } else { stk . push ( stk . pop () / v ); } sign = c ; v = 0 ; } } int ans = 0 ; while (! stk . isEmpty ()) { ans += stk . pop (); } return ans ; } }

1class Solution { public: int calculate ( string s ) { int v = 0 , n = s . size (); char sign = '+' ; stack < int > stk ; for ( int i = 0 ; i < n ; ++ i ) { char c = s [ i ]; if ( isdigit ( c )) v = v * 10 + ( c - '0' ); if ( i == n - 1 || c == '+' || c == '-' || c == '*' || c == '/' ) { if ( sign == '+' ) stk . push ( v ); else if ( sign == '-' ) stk . push ( - v ); else if ( sign == '*' ) { int t = stk . top (); stk . pop (); stk . push ( t * v ); } else { int t = stk . top (); stk . pop (); stk . push ( t / v ); } sign = c ; v = 0 ; } } int ans = 0 ; while ( ! stk . empty ()) { ans += stk . top (); stk . pop (); } return ans ; } };

1class Solution : def calculate ( self , s : str ) -> int : v , n = 0 , len ( s ) sign = '+' stk = [] for i , c in enumerate ( s ): if c . isdigit (): v = v * 10 + int ( c ) if i == n - 1 or c in '+-*/' : if sign == '+' : stk . append ( v ) # for "10-2*5": when '-' encountered, var 'sign' is still '+' # so '10' will be pushed to stk before setting sign to '-' elif sign == '-' : stk . append ( - v ) elif sign == '*' : stk . append ( stk . pop () * v ) elif sign == '/' : stk . append ( int ( stk . pop () / v )) else : print ( "operator not supported" ) sign = c # reset inside 'if' v = 0 return sum ( stk )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem