Basic Calculator II — Stack with Operator Precedence

Sanjeev SharmaSanjeev Sharma
1 min read

Advertisement

Problem 283 · Basic Calculator II

Difficulty: Medium · Pattern: Stack + Operator Precedence

Evaluate expression with +, -, *, / (no parentheses).

Intuition

Scan left to right. For + and -, push value. For * and /, pop top, compute, push result. Sum the stack at end.

Solutions

# Python
def calculate(s):
    stack = []
    num = 0; op = '+'
    for i, c in enumerate(s):
        if c.isdigit(): num = num*10 + int(c)
        if (not c.isdigit() and c != ' ') or i == len(s)-1:
            if op == '+': stack.append(num)
            elif op == '-': stack.append(-num)
            elif op == '*': stack.append(stack.pop()*num)
            elif op == '/': stack.append(int(stack.pop()/num))  # truncate toward zero
            op = c; num = 0
    return sum(stack)
// Java
public int calculate(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    int num=0; char op='+';
    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(op=='+') stack.push(num);
            else if(op=='-') stack.push(-num);
            else if(op=='*') stack.push(stack.pop()*num);
            else stack.push((int)((double)stack.pop()/num));
            op=c; num=0;
        }
    }
    return stack.stream().mapToInt(i->i).sum();
}

Complexity

  • Time: O(n)
  • Space: O(n)

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro