001package algs13;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac Evaluate.java
005 *  Execution:    java Evaluate
006 *  Dependencies: Stack.java
007 *
008 *  XEvaluates (fully parenthesized) arithmetic expressions using
009 *  Dijkstra's two-stack algorithm.
010 *
011 *  % java Evaluate
012 *  ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )
013 *  101.0
014 *
015 *  % java Evaulate
016 *  ( ( 1 + sqrt ( 5 ) ) / 2.0 )
017 *  1.618033988749895
018 *
019 *
020 *
021 *  Remarkably, Dijkstra's algorithm computes the same
022 *  answer if we put each operator *after* its two operands
023 *  instead of *between* them.
024 *
025 *  % java Evaluate
026 *  ( 1 ( ( 2 3 + ) ( 4 5 * ) * ) + )
027 *  101.0
028 *
029 *  Moreover, in such expressions, all parentheses are redundant!
030 *  Removing them yields an expression known as a postfix expression.
031 *  1 2 3 + 4 5 * * +
032 *
033 *
034 *************************************************************************/
035
036public class XEvaluate {
037        public static void main(String[] args) {
038                Stack<String> ops  = new Stack<>();
039                Stack<Double> vals = new Stack<>();
040
041                StdIn.fromString ("( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )");
042                //StdIn.fromString ("( ( 1 + sqrt ( 5 ) ) / 2.0 )");
043
044                while (!StdIn.isEmpty()) {
045                        String s = StdIn.readString();
046                        if      (s.equals("("))               ;
047                        else if (s.equals("+"))    ops.push(s);
048                        else if (s.equals("-"))    ops.push(s);
049                        else if (s.equals("*"))    ops.push(s);
050                        else if (s.equals("/"))    ops.push(s);
051                        else if (s.equals("sqrt")) ops.push(s);
052                        else if (s.equals(")")) {
053                                String op = ops.pop();
054                                double v = vals.pop();
055                                if      (op.equals("+"))    v = vals.pop() + v;
056                                else if (op.equals("-"))    v = vals.pop() - v;
057                                else if (op.equals("*"))    v = vals.pop() * v;
058                                else if (op.equals("/"))    v = vals.pop() / v;
059                                else if (op.equals("sqrt")) v = Math.sqrt(v);
060                                vals.push(v);
061                        }
062                        else vals.push(Double.parseDouble(s));
063                }
064                StdOut.println(vals.pop());
065        }
066}