package algorithms.util;

 import algorithms.ADT.Stack;

 /******************************************************************************

  *  Compilation:  javac Evaluate.java

  *  Execution:    java Evaluate

  *  Dependencies: Stack.java

  *

  *  Evaluates (fully parenthesized) arithmetic expressions using

  *  Dijkstra's two-stack algorithm.

  *

  *  % java Evaluate

  *  ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

  *  101.0

  *

  *  % java Evaulate

  *  ( ( 1 + sqrt ( 5 ) ) / 2.0 )

  *  1.618033988749895

  *

  *

  *  Note: the operators, operands, and parentheses must be

  *  separated by whitespace. Also, each operation must

  *  be enclosed in parentheses. For example, you must write

  *  ( 1 + ( 2 + 3 ) ) instead of ( 1 + 2 + 3 ).

  *  See EvaluateDeluxe.java for a fancier version.

  *

  *

  *  Remarkably, Dijkstra's algorithm computes the same

  *  answer if we put each operator *after* its two operands

  *  instead of *between* them.

  *

  *  % java Evaluate

  *  ( 1 ( ( 2 3 + ) ( 4 5 * ) * ) + )

  *  101.0

  *

  *  Moreover, in such expressions, all parentheses are redundant!

  *  Removing them yields an expression known as a postfix expression.

  *  1 2 3 + 4 5 * * +

  *

  *

  ******************************************************************************/

 public class Evaluate {

     public static void main(String[] args) {

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

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

         while (!StdIn.isEmpty()) {

             String s = StdIn.readString();

             if      (s.equals("("))               ;

             else if (s.equals("+"))    ops.push(s);

             else if (s.equals("-"))    ops.push(s);

             else if (s.equals("*"))    ops.push(s);

             else if (s.equals("/"))    ops.push(s);

             else if (s.equals("sqrt")) ops.push(s);

             else if (s.equals(")")) {

                 String op = ops.pop();

                 double v = vals.pop();

                 if      (op.equals("+"))    v = vals.pop() + v;

                 else if (op.equals("-"))    v = vals.pop() - v;

                 else if (op.equals("*"))    v = vals.pop() * v;

                 else if (op.equals("/"))    v = vals.pop() / v;

                 else if (op.equals("sqrt")) v = Math.sqrt(v);

                 vals.push(v);

             }

             else vals.push(Double.parseDouble(s));

         }

         StdOut.println(vals.pop());

     }

 }