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}