ADT Stack

Objectives

- To gain understanding of how an implementation of an ADT is used by an application program.
- To learn how expressions can be evaluated at run-time.
- To become familiar with how infix expressions can be converted to postfix expressions.

Task

Write a Java program (a collection of Java classes) including a class named ExpressionCalculator that contains a static main method. This main method will prompt the user to enter a constant expression (i.e., a mathematical expression without variables) at the keyboard. The expression must be in infix notation and must use spaces to separate the tokens (operands and operators) of the expression. (This restriction is imposed to simplify the parsing of the input.) The only exception to the space-separation rule is for the unary minus prefix operator, which will be assumed to be part of the specification of a negative constant operand. The program will then evaluate the expression and display the result on the console. It will then wait for another expression to be entered for evaluation, terminating on an empty input.

The following operators should be supported by your expression calculator:

The algorithm for the infix-to-postfix converter is as follows:

while there are more tokens in the infix string get the next token
if the next token is an operand append it to the postfix expression
else if the next token is an operator process the operator (see below)
else
indicate a syntax error
pop the remaining operators off the operator stack and append them to the postfix expression, but indicate a syntax error if a '(' is found

The algorithm for processing an operator is:

if the operator stack is empty or
the item on top of the stack is '('

push the current operator onto the stack
else
fetch the top operator on the stack
if the precedence of the current operator is greater than the precedence of the top operator from the stack
push the current operator onto the stack
else
while the stack is not empty and
the operator on top of the stack is not '(' and
the precedence of the current operator is less than or equal to the precedence of the top operator on the stack
pop the top operator off the stack and append it to the postfix

expression

if the operator stack is not empty
fetch the top operator from the stack

if the operator on top of the stack is '(' pop the top element of the stack
if the current operator is not ')'
push the current operator onto the stack

You can also use the algorithms in the text-book if you like. You can also adjust them as needed to allow for the correct processing of right-associative unary operators. If some of those operations cannot be complemented, that is fine.

You can use the algorithm for postfix expression evaluator in the textbook.

Hints

Use a StringBuffer or the new StringBuilder class of Java 5 for the postfix expression as it is being constructed. It is more efficient to make many modifications to a StringBuffer or to append() strings to a StringBuilder than to continually create new Strings by appending to existing ones.

Use Java's StringTokenizer or the new Scanner class of Java 5 to parse expressions. The latter offers the methods hasNextType and nextType (where Type is replaced by Integer, Double, etc.), which would be convenient for checking if the next token in an expression can be parsed as a Double and is thus an operand.