Scale Engineer

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
StringStack
Companies
AccentureAirbnbByteDanceDoorDash

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 [-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 * 105
  • 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, 231 - 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

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

Walkthrough

The idea is to process the expression in two steps:

  1. 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
  1. Second pass: Process addition and subtraction
  • Sum up all numbers in the stack considering their signs

Here's the implementation:

public int calculate(String s) {    Stack<Integer> stack = new Stack<>();    char lastOp = '+';    int num = 0;        for (int i = 0; i < s.length(); i++) {        char c = s.charAt(i);                if (Character.isDigit(c)) {            num = num * 10 + (c - '0');        }                if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {            if (lastOp == '+') {                stack.push(num);            } else if (lastOp == '-') {                stack.push(-num);            } else if (lastOp == '*') {                stack.push(stack.pop() * num);            } else if (lastOp == '/') {                stack.push(stack.pop() / num);            }            lastOp = c;            num = 0;        }    }        int result = 0;    while (!stack.isEmpty()) {        result += stack.pop();    }    return result;}

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

Solutions

using 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 ; } }

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 →

Next problem