Program 2 – AS/AK/ITEC 2620 3.0, Section M

Purpose

1. To work with grammars and search trees.
2. To use stacks and queues.

"RPN" (Reverse Polish Notation)

RPN is equivalent to a post-operator notation.  Unlike the more common in-order notation (i.e. firstTerm operator secondTerm), RPN has the operator after the two terms (i.e. firstTerm secondTerm operator).  One of the benefits of RPN is that order of operations can be specified without brackets.  For example:
5 + 4 / 2 = 7
(5+4) / 2 = 4 (integer division)

5 4 2 / + = 7
5 4 + 2 / = 4

Specifically, operators are always processed as they are encountered.  The processing of operators is best explained using a stack.  As numbers are entered, they are pushed onto a stack.  When an operator is encountered, two operands are popped off of the stack, and the result is pushed back onto the stack.  For example:
5 4 + 2 /

push(5)
push(4)
secondTerm = pop()
firstTerm = pop()
push(firstTerm + secondTerm)
push(2)
secondTerm = pop()
firstTerm = pop()
push(firstTerm / secondTerm)
result = pop()

A four-function RPN calculator

For this project, you are to implement a four-function RPN calculator.  This calculator can only subtract 1 from a number, divide (using integer division) a number by 2, multiply 3 to a number, and add 4 to a number.  Also, you may only enter the numbers 1, 2, 3, and 4 into the calculator.  Therefore, your four functions are
n 1 -
n 2 /
3 n *
4 n +

where n = 1, 2, 3, 4

Error checking

For this project, you must use a BFS search tree and the following grammar to validate the equation before it is fed into the calculator:
G = {T, N, S, P}
T = {-, /, *, +, 1, 2, 3, 4}
N = {V, n}
S = V

V => V 1 -
V => V 2 /
V => 3 V *
V => 4 V +
V => n
n => 1
n => 2
n => 3
n => 4

Input/Output

The program input will be a String of characters (i.e. terminals).

The program output should state whether or not the equation is valid, how many search nodes were created by your BFS validater, and the value of the equation if it is valid.

Examples

In order to test your program, the following sample input and output are provided.  Thus, if your program is implemented correctly, the following two commands should create the sample output:
javac Program2.java
java Program2 input2_1.txt

Submission

Submit only the file Program2.java using the standard on-line instructions.  Note: your program will likely require you to import existing JAVA classes (e.g. LinkedList) or to develop support classes.  If you choose to develop your own support classes, submit them in the file Program2.java the same way that you submitted LinkedList, BSTBase, BSTSlow, and BSTFast in program 1 (i.e. as non-public classes).

Specifically, to submit and confirm submission, type:

submit 2620 a2 Program2.java
showsub 2620 a2
Note: depending on the stability of the submit program, you may have to do this from your home directory.

Marking

The program will be marked out of 20 -- 5 for style and 15 for program execution.
Style Execution