I am reading, experimenting with the examples and working on some (do not have enough time to address them all) exercises using the Algorithms fourth edition book by Robert Sedgewick and Kevin Wayne. I am having a good time refreshing and learning some new things.
This morning I was reading Dijkstra’s Two-Stack Algorithm for Expression Evaluation on page 129. The algorithm is well explained and works. What called my attention is that the actual code does not seem to work on my machine. I already sent a message to professor Sedgewick for clarification.
The authors mention a couple times that the implementation is partial in the sense that several conditions are not addressed. That makes sense due to the scope of the book and the fact that the example works as long as you enclose all expressions with enough parenthesis.
In order for the example to operate I had to add a parenthesis count. Unless I am missing something, it seems like the StdIn.isEmpty() method would not work as expected.
Following is my take on the exercise:
package edu.princeton.cs.algs4;
import java.util.Stack;
public class Evaluate {
public static void main(String[] args) {
Stack<String> ops = new Stack<String>();
Stack<Double> vals = new Stack<Double>();
int count = 0;
// **** loop parsing the expression ****
StdOut.print(“>>> expression: “);
// while (!StdIn.isEmpty()) {
do {
// **** read the next input string ****
String s = StdIn.readString();
// **** process the string ****
switch (s) {
case “(“:
// **** increment the parenthesis count ****
count++;
break;
case “+”:
case “-“:
case “*”:
case “/”:
case “sqrt”:
ops.push(s);
break;
case “)”:
// **** ****
String op = ops.pop();
// **** pop the next value ****
Double v = vals.pop();
// **** evaluate and push result ****
switch (op) {
case “+”:
v = vals.pop() + v;
break;
case “-“:
v = vals.pop() – v;
break;
case “*”:
v = vals.pop() * v;
break;
case “/”:
v = vals.pop() / v;
break;
case “sqrt”:
v = Math.sqrt(v);
break;
}
// **** push the new value into the stack ****
vals.push(v);
// **** decrement the parenthesis count ****
count–;
break;
default:
vals.push(Double.parseDouble(s));
break;
}
} while (count != 0);
// **** display the result ****
StdOut.print(“<<< result: ” + vals.pop());
}
}
You can take a look at the original code in the book. I changed the while() in order for it to complete. Without this modification it would just hang waiting for additional input. In the following URL: http://docs.oracle.com/javase/7/docs/api/java/util/Scanner.html#hasNext() you may find the description of the Scanner.hasNext() method. Of interest is the following paragraph:
“public boolean hasNext()
Returns true if this scanner has another token in its input. This method may block while waiting for input to scan. The scanner does not advance past any input.”
Given that for simplicity the code requires parenthesis, the modified version requires for the entire expression to be enclosed in parenthesis. For example, the following expression:
( 1 + sqrt ( ( ( ( ( ( 6 + 4 ) * ( 9 – 3 ) ) + 3 ) / 3 ) + 4 ) ) )
Evaluates to:
( 1 + sqrt ( ( ( ( ( ( 10 ) * ( 6) ) + 3 ) / 3 ) + 4 ) ) )
( 1 + sqrt ( ( ( ( ( 60 ) + 3 ) / 3 ) + 4 ) ) )
( 1 + sqrt ( ( ( 21 ) + 4 ) ) )
( 1 + sqrt ( ( 25 ) ) )
( 1 + 5 )
6
The program as illustrated by the following screen capture produces the same result:
>>> expression: ( 1 + sqrt ( ( ( ( ( ( 6 + 4 ) * ( 9 – 3 ) ) + 3 ) / 3 ) + 4 ) ) )
<<< result: 6.0
One could also read the entire expression in one line with StdIn.readLine() and then parse the string. Then the program may continue to loop until some agreed upon sequence (e.g., done, exit) is entered or exit on control-z. Please keep in mind that the object of the example and for that matter the book is to learn and experiment with algorithms. So far so good :o)
By the way, I did receive a response to my message from Kevin Wayne. Kevin acknowledges that the program would wait indefinitely for input. On a separate note, Kevin replied Sunday afternoon. I was expecting a reply no earlier than Monday morning. Such event indicates passion on the side of the authors. That is one (if not the most) of the most important and desired professional qualities on individuals!!!
If you have comments or questions, please do not hesitate and send me a message.
John
john.canessa@gmail.com