Leetcode - Basic Calculator II

Question

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().

Ideas

• The trick here is that you need to recognize that we need to consider PEMDAS and our order of operations which means we evaluate * and / before + and -
• In general, we want to use a stack since we may want to immediately handle an operator (*, /) where our operators affect how we apply to our stack
  • Ex.
    • • just appends our current int to the stack
    • • makes our current int negative and appends to the stack
    • * pops the last element in the stack, multiplies that with our current int and then adds that to the stack
    • / applies itself like /* except we int floor
• A challenge here is that two elements in a row are kind of coupled (1+3*3) which we can handle by tracking our pending operation, and applying it to the integer after that operation when we run into another operation (because that means we are done building our integer)
• An edge case here is that since the string doesn’t end in an operation, we never consider the last number, we can fix this by just appending a ‘+’ to the very end of the string

Solution