LeetCode – 224. Basic Calculator , Interview question

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

Note:Do not use the eval built-in library function.

Solution

This is a simple calculator which can add and subtract and support braces.

  • We will start with creating a map object which will have all the operators. For example – +, -, ( and ).
  • Map will contain priority and execute function if needed for that operator.
  • Next step is to split string by operators and obtain array.
  • We will need two stacks – operandStack and operatorStack.
  • If operand is encountered then we will just push that item to operandStack.
  • Calc function is created which will just pop two operands from an top of operandStack and pop one operator from operatorStack. Then it will call execute function from map corresponding to popped operator on operands and then push the result to top of operandStack.
  • If operator is encountered then –
    • if operator is ‘(‘ then just push operator to operatorStack.
    • if operator ‘)’ then call the calculate function until next ‘)’ is popped from stack.
    • Else if any other operator is encountered then check current operator’s priority with operator on top of stack. If current priority is lower then value on top of stack then pop that value and call corresponding execute function on top elements of operandStack. If current priority is higher then just push it on operator stack.
  • After processing the whole operator array check if anything is pending on operator stack. If yes then process all operators by calling calc function.
  • In the end there will only be one value on top of operandStack which is final result.
     

    LeetCode Question – https://leetcode.com/problems/basic-calculator/description/

Leave a Reply

Your email address will not be published. Required fields are marked *