Last active
July 16, 2018 22:24
-
-
Save adnauseum/e443217890e6dfca182051c226854fa2 to your computer and use it in GitHub Desktop.
Dijkstra's two-stack algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/****************************************************************************** | |
* 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 | |
* | |
* | |
* | |
* 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()); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment