CPSC 170 Spring 2002
Program 3: Postfix Evaluation
Due Wednesday, April 3, 2002
Background
We are accustomed to writing arithmetic expressions in infix
notation, which means that the operator appears between the operands:
3 * ((4 + 6) / 2)
An alternative is to use postfix notation, which means that the
operator appears after the operands. The expression below is
equivalent to the infix expression above:
3 4 6 + 2 / *
One advantage of postfix is that unlike infix, no parentheses are
necessary. Another advantage is that postfix expressions are
easily evaluated using a stack. This is done by processing the
expression from left to right as follows:
- When you encounter an operand, push it on the stack.
- When you encounter an operator op, pop the top two
operands off the stack. Say x gets the first value popped and y gets
the second value popped; compute y op x and push the result onto
the stack.
- When the entire expression has been processed, the stack should
contain exactly one value -- the answer.
Problem
Your assignment is to write a class Postfix with a method
public static int eval(String exp) that takes a String representing an
integer
postfix expression and returns its
value. Expression exp
should be space delimited, that is, operands and operators should
be separated by one or more spaces. Also write a class EvalPostfix that
prompts the user for a postfix expression and evaluates it
using the eval method of the Postfix class.
Approach
Use a StringTokenizer to extract the pieces of the input expression.
(See p. 206-210 for a description and examples.) Note that
by default StringTokenizer assumes that the string is space delimited.
Then use a Java Stack to evaluate the expression. Note that a Stack can
hold only Objects, but since a StringTokenizer always returns a String, and
a String is an Object, you're all set. You will, of course, have
to extract numbers from the strings before you can do calculations
with them; you can use the parseInt method of the Integer class
for this.
Be sure to document your program.