package algs13;
import stdlib.*;
import java.util.TreeMap;
/* ***********************************************************************
 *  Compilation:  javac EvaluateDeluxe.java
 *  Execution:    java EvaluateDeluxe
 *  Dependencies: Stack.java
 *
 *  Evaluates arithmetic expressions using Dijkstra's two-stack algorithm.
 *  Handles the following binary operators: +, -, *, / and parentheses.
 *
 *  % echo "3 + 5 * 6 - 7 * ( 8 + 5 )" | java EvaluateDeluxe
 *  -58.0
 *
 *
 *  Limitiations
 *  --------------
 *    -  can easily add additional operators and precedence orders, but they
 *       must be left associative (exponentiation is right associative)
 *    -  assumes whitespace between operators (including parentheses)
 *
 *  Remarks
 *  --------------
 *    -  can eliminate second phase if we enclose input expression
 *       in parentheses (and, then, could also remove the test
 *       for whether the operator stack is empty in the inner while loop)
 *    -  see http://introcs.cs.princeton.edu/java/11precedence/ for
 *       operator precedence in Java
 *
 *************************************************************************/

public class XEvaluateDeluxe {

  // result of applying binary operator op to two operands val1 and val2
  public static double eval(String op, double val1, double val2) {
    if (op.equals("+")) return val1 + val2;
    if (op.equals("-")) return val1 - val2;
    if (op.equals("/")) return val1 / val2;
    if (op.equals("*")) return val1 * val2;
    throw new Error("Invalid operator");
  }

  public static void main(String[] args) {

    StdIn.fromString ("1 + 2 + 3");

    // precedence order of operators
    TreeMap<String, Integer> precedence = new TreeMap<>();
    precedence.put("(", 0);   // for convenience with algorithm
    precedence.put(")", 0);
    precedence.put("+", 1);   // + and - have lower precedence than * and /
    precedence.put("-", 1);
    precedence.put("*", 2);
    precedence.put("/", 2);

    Stack<String> ops  = new Stack<>();
    Stack<Double> vals = new Stack<>();

    while (!StdIn.isEmpty()) {

      // read in next token (operator or value)
      String s = StdIn.readString();

      // token is a value
      if (!precedence.containsKey(s)) {
        vals.push(Double.parseDouble(s));
        continue;
      }

      // token is an operator
      while (true) {

        // the last condition ensures that the operator with higher precedence is evaluated first
        if (ops.isEmpty() || s.equals("(") || (precedence.get(s) > precedence.get(ops.peek()))) {
          ops.push(s);
          break;
        }

        // evaluate expression
        String op = ops.pop();

        // but ignore left parentheses
        if (op.equals("(")) {
          if (!s.equals(")")) throw new Error ();
          break;
        }

        // evaluate operator and two operands and push result onto value stack
        else {
          double val2 = vals.pop();
          double val1 = vals.pop();
          vals.push(eval(op, val1, val2));
        }
      }
    }

    // finished parsing string - evaluate operator and operands remaining on two stacks
    while (!ops.isEmpty()) {
      String op = ops.pop();
      double val2 = vals.pop();
      double val1 = vals.pop();
      vals.push(eval(op, val1, val2));
    }

    // last value on stack is value of expression
    StdOut.println(vals.pop());
    if (!vals.isEmpty()) throw new Error ();
    if (!ops.isEmpty()) throw new Error ();
  }
}