01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
package algs13;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac Evaluate.java
 *  Execution:    java Evaluate
 *  Dependencies: Stack.java
 *
 *  XEvaluates (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
 *
 *
 *
 *  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 XEvaluate {
  public static void main(String[] args) {
    Stack<String> ops  = new Stack<>();
    Stack<Double> vals = new Stack<>();

    StdIn.fromString ("( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )");
    //StdIn.fromString ("( ( 1 + sqrt ( 5 ) ) / 2.0 )");

    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());
  }
}