227. Basic Calculator II

-
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
Example 1:
Input: "3+2*2"
Output: 7
Example 2:
Input: " 3/2 "
Output: 1
Example 3:
Input: " 3+5 / 2 "
Output: 5
Note:
  • You may assume that the given expression is always valid.
  • Do not use the eval built-in library function.
---
Intuition

Skip spaces, Track of operator before isNegative, isMulti, isDivi, if isDivi, collect consecutive digits into num, decrement i. if Negative, push -1 * num, if Multi push stack.poll() * num, if Divi push stack.poll() / num else push num onto stack. reset isMulti, isDivi, isDivi after pushing to stack
---
 Two stacks 1 for operand, 1 for operator
push integers onto one stack, operators on second
if we see * or / operator - generate result of next number from stack, and peek of operand stack, and push result to operand stack.

 In the end, combine the remaining operands, with remaining operators + or -
---
Time - O(N)
Space - O(N)
---
Related problems
---