Evaluating Reverse Polish Notation Expressions

Overview

The purpose of this assignment is to exercise your ability to implement a command-line program involving elementary string tokenization, and the manipulation of a stack.

Background

Via Wikipedia: Reverse Polish notation (RPN) is a mathematical notation in which every operator follows all of its operands, in contrast to Polish notation (PN), which puts the operator before its operands. It is also known as postfix notation. It does not need any parentheses as long as each operator has a fixed number of operands. The description Polish refers to the nationality of logician Jan ukasiewicz, who invented Polish notation in the 1920s.

The reverse Polish scheme was proposed in 1954 by Burks, Warren, and Wright and was independently reinvented by Friedrich L. Bauer and Edsger W. Dijkstra in the early 1960s to reduce computer memory access and utilize the stack to evaluate expressions. The algorithms and notation for this scheme were extended by Australian philosopher and computer scientist Charles Hamblin in the mid1950s.

Specification

For this assignment you are to define a program RPNCalculator which outputs every expression and its corresponding value in the given input file(s). As an example, consider the following file test-1.txt:

5 4 + 3 2 + 5 * 

Running the command java RPNCalculator test-1.txt should have the following output:

$ java RPNCalculator test-1.txt test-1.txt: 5 4 + 9 3 2 + 5 * 25 

If we include the file test-2.txt whose contents are as follows:

3 3 - 5 4 + * 10 8 3 + - 

The running the command java RPNCalculator test-1.txt test-2.txt should have the following output:

$ java RPNCalculator test-1.txt test-2.txt test-1.txt: 5 4 + 9 3 2 + 5 * 25 test-2.txt: 3 3 - 5 4 + * 0 10 8 3 + - -1 

File Format

For this assignment you may assume the following file format:

Files will be saved as plain text.

If the file is not empty, then it will have exactly one RPN expression per line, and no expressions will span multiple lines.

You may assume that the kinds of expressions you will be given are integer expressions, and will be comprised of the following operators: + (addition), - (subtraction), * (multiplication), / (integer division), and % (modulus).

The individual symbols that comprise an expression will be separated by one or more whitespace characters. Strings which are comprised of one or more whitespace characters can be identified in Java using the regular expression "\\s+".

Considerations

For this assignment, you may not assume that the expressions are guaranteed to be syntactically, or semantically correct. If the file contains a malformed expression, you must find and print the first error found instead of evaluating the expression. For example, consider the file test-3.txt:

5 4 3 + - -2 1 + 10 9 

Running the command java RPNCalculator test-3.txt should have the following output (the actual error messages are up to you, but should at least inform the user what the offending expression was, and the general nature of the error):

$ java RPNCalculator test-3.txt test-3.txt: 5 4 3 + - -2 1 +: invalid expression 10 9: invalid expression 

If we add the expression 5 4 4 - / to the end of test-3.txt, re-running the command should output the following:

$ java RPNCalculator test-3.txt test-3.txt: 5 4 3 + - -2 1 +: invalid expression 10 9: invalid expression 5 / 0: will cause a division by zero error 

Note that this is an example of a semantic error, the new expression is syntactically correct, but is still not well-defined.

Lastly, you may not assume that the given file actually exists, and is necessarily readable, and consequently have to gracefully handle potentialIOExceptions. In this case, it is sufficient to simply output a message stating that the given file cannot be processed.

$ java RPNCalculator foo.txt foo.txt: unable to process file 

Hints

String tokenization is outside of the scope of this course, so one way to accomplish this in Java is the following:

String[] tokens = expression.split("\\s+"); 

Note that for this instruction to work, expression must be an object of the type String.

Similarly, as was discussed in class, properly classifying a string as an integer is also outside of the scope of this class (and is in general not as trivial as it may seem), and may be accomplished by the following function:

// isLong: String -> Boolean // If x is a String, then isLong(x) is true if and only if // x represents a valid long in the Java programming language. public static boolean isLong(String x) { try { Long.parseLong(x); return true; } catch (NumberFormatException exception) { return false; } } 

It should be noted however that this particular mechanism, while simple enough to understand, is not a preferred solution to this particular problem.