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 (InvalidExpressionException e) {
System.out.println(e);
}
}
}
Here you should note that the evaluate method can throw an InvalidExpressionException if there is something wrong with the expression. Your evaluate method should do the same.
Your evaluate code will need to use the Stack class. You may want to start with one of the Stack implementations found in the lab4 directory. These implementations are not fully tested and debugged but should save you some time in creating your Stack class. Also, you will want your Stack class to throw an EmptyStackException whenever it tries to access the top item of an empty stack. To help with the exceptions, the class definitions for the two exceptions that you need are already available in the lab4 directory.
For submitting your lab assignment turn in the following hard copies: