Basic Calculator II — Stack with Operator Precedence
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