For this lab, you will create a program that uses a stack to evaluate reverse Polish expressions. If you have ever worked with a Hewlett-Packard calculator, you have already seen reverse Polish notation. Under this notation, operators appear after their operands in an expression. For example, the following expression adds the numbers 3 and 5:
3 5 +
The advantage of reverse Polish notation is that it makes parentheses unnecessary. For example, the following expression
(3 + 2) * (1 + (2 * 5))can be written in reverse Polish notation without parentheses.
3 2 + 1 2 5 * + *
Reverse Polish expressions can be evaluated very efficiently using a stack. The basic algorithm traverses the expression, looking at each token, (integer or operator), and performing the following:
After the entire expression has been traversed, the value of the expression will be sitting on the top of the stack.
The StringTokenizer in the util package is useful here since it provides an iterator for stepping through the individual tokens in the expression. It returns each token as a string. An operator can be detected by checking the first character of a string. Otherwise, you can assume that the token is an integer and place it on the stack as a string. Later, if that string fails to be parsed as an integer, your method can throw an exception.
In writing your program, you should create the file Calc.java, which
defines an evaluate method so that your program could run with code similar
to the following:
public static void main (String [] args)
{
EasyReader stdin = new EasyReader(System.in);
while (!stdin.isEOF()) {
String expression = stdin.stringInputLine();
System.out.println("Processing: " + expression);
try {
System.out.println(evaluate(expression));
}
catch (Exception e) {
System.out.println(e);
}
}
}
Here you should note that the evaluate method can throw an exception if there is something wrong with the expression. Your evaluate method should do the same. This example uses the EasyReader class described in the text.
Your evaluate code will need to use a stack class. You may simply use the ObjectStack class described in the text. Note that the stack class throws an EmptyStackException whenever it tries to access the top item of an empty stack. Your evaluate method should catch all exceptions and throw a new, more meaningful exception that describes the problem with the expression.
Before the due date and time, you should submit the following file through the submission Web page: