Day 2: Postfix Expression Evaluation

Exercise

Write a Java program to compute the value of an arithmetic expression written in postfix notation.

Introduction

Postfix notation, also known as Reverse Polish notation or RPN, is a method of writing arithmetic and algebraic expressions in which all operators follow their operands (contrast this with infix notation, the more familiar method). For example:

4 6 +
12 3 / 4 +
5 28 14 - * 2 / 49 7 / +

These expressions would be written in infix as:

4 + 6
12 / 3 + 4
5 * (28 - 14) / 2 + (47 / 7)

The primary advantage to using postfix notation is there is no need to explicitly describe precedence using parentheses. This simplifies machine evaluation significantly.

Machine evaluation is done using a structure known as a stack. The stack structure implements an idea know as Last In First Out (LIFO). This means, simply, the last object added is the first object to be removed. Objects are added (pushed) and removed (popped) from only one end of the stack. An analogy for a stack is a literal stack of papers, but you can only put papers on the top of this stack. Likewise, you can only take papers off the top of the stack.

Algorithm

Familiarize yourself with the postfix algorithm.
Implement the core functionality using a text-based interface for I/O.
Build a GUI to wrap your implementation.

Resources

Main.java (text-based interface)
A Postfix Calculator
Reverse Polish notation (Wikipedia)
Stack data structure (Wikipedia)

Hints

To split an expression into individual operators and operands, use the split function in the String class.
Use the ArrayDeque class in the Java API for your stack.
To keep your implementation simple, assume all input will be correct and don't worry about the errors described in the postfix algorithm. If you have time, add error handling.
Start by implementing the four basic arithmetic operations: addition, subtraction, multiplication, and division.
After you implement those, try implementing exponentiation or trigonometry functions. Consult the Java API, specifically the Math class, when implementing these functions.