package lc.reversepolishnotation;

import java.util.Stack;
/*
Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:
  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

  More info about RPN refer to  https://en.wikipedia.org/wiki/Reverse_Polish_notation
*/
// The benefit of Reverse Polish Notation is the absence of parentheses
public class Solution {
  // Q1: is the incoming expression always valid?
  // Q2: will there be any negative integer?
  // Q3: Overflow cases? Need to handle them or not?
  // The following alg assume the existence of negative numbers. Runtime: O(n), space: O(n)
  // depends on the number of operands in expression(can take up to 2/3 of tokens, due to that
  // one operator need to corresponds to two operands).
  public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    int len = tokens.length;
    for (int i = 0; i < len; i++) {
      String curr = tokens[i];
      // need to catch negative number
      if (Character.isDigit(curr.charAt(0)) || (curr.length() > 1 && Character.isDigit(curr.charAt(1))))
        stack.push(Integer.valueOf(curr)); // number
      else {
        // operator, we don't need to put operator into stack, instead we directly compute the result
        // associated with the operator and push result back to stack
        int right = stack.pop();
        int left = stack.pop();
        int re = 0;

        if (curr.equals("+"))
          re = right + left;
        else if (curr.equals("-"))
          re = left - right;
        else if (curr.equals("*"))
          re = left * right;
        else if (curr.equals("/"))
          re = left / right;
        stack.push(re);
      }
    }

    return stack.pop();
  }
}