JAVA program- expressions with queues and stacks

In prefix notation, an operator is written in front of its two operands in the format

operator op1 op2, IE: + 3 4 this is the same as 3 + 4?In postfix notation, an operator is written after its two operands: op1 op2 operator,

IE: 3 4 + and is again equivalent to 3+4?In both prefix and postfix notation the order of operands is the same as the original infix

expression.

2 * ( 3 + 4) 2 3 4 + * * 2 + 3 4

and operators can be scattered throughout the expression. One thing true of all expressions regardless of notation is that the number of operands equals the number of operators plus 1.

For simplicity, we will only consider the operators + - / * and %. Also, all operands will initially be a number of type double: IE:

* + 9.3 4.5 - 3 1

Each token or piece of the expression will always be separated by at least one space.

Interface for class Expression

public Expression( String str) : This constructor receives a String containing the expression text. It will then break the expressions into tokens (individual symbols separated by spaces) and store the resulting String array into the data member tokenList.

protected static boolean isOperand(String str): returns true if the String parameters is a valid operand (double number)

protected static double getOperandValue(String str): given a String containing a valid operand this method returns the value of the operand as type double.

protected static boolean isOperator(String str): returns true if the String parameter contains one of +, -, *, / or %.

public String getExpression(): returns the expression string.

public ArrayList getTokens(): returns the token list

protected static double evaluateSubExpression( double operand1, String operator, double operand2): This method evaluates a subexpression as:

operand1 operator operand2

and returns the result as type double.

public abstract boolean isLegal(): abstract method to be implement in each subclass.* public abstract double evaluate(): abstract method to be implement in each subclass.

Interface for class PrefixExpression

public PrefixExpression( String str) : This constructor receives a String containing the expression text. It will invoke the constructor for class Expression, passing in the expression text.

public boolean isLegal(): This method returns true if the first token in the tokenList is an operator, AND the last two tokens are operands, AND the number of operands in the expression is equal to the number of operators plus 1.

public double evaluate(): This method uses a queue of Strings to evaluate the prefix expression.

o Ensure the expression is legal, if not Stop and throw an exception, using class ArithmeticException

o Enqueue all of the tokens in the tokenList into the queue o if the # of tokens in the queue >= 3,

? Dequeue the 1st 3 values. Into 3 String variables: ie: a, b, & c ? else Stop and throw an exception, using class

ArithmeticException o While not done

? If A is not an operator, and B & C are not operands, then we do not have a subexpression. So;

Enqueue A back onto the queue, and swap values ?

A =B ?

B=C ?

Dequeue a new value into C ?

Repeat the previous steps until A is an operator and B & C operands ?

? Once is we have a subexpression ?

Convert the operands into values of type double ?

Call the method evaluateSubexpression ?

Enqueue the result back onto the queue. ?o If the number of elements in the queue equals 1, we are done. ?o Else, dequeued 3 new values into a , b, & c and continue processing. ?

o When done (one value remaining on the queue) dequeue and return the result of the expression.

Interface for class PostfixExpression

public PostfixExpression( String str) : This constructor receives a String containing the expression text. It will invoke the constructor for class Expression, passing in the expression text.

public boolean isLegal(): This method returns true if the last token in the tokenList is an operator, AND the first two tokens are operands, AND the number of operands in the expression is equal to the number of operators plus 1.

public double evaluate(): This method uses a stack of type Double to evaluate the postfix expression.

o Ensure the expression is legal, if not Stop and throw an exception, using class ArithmeticException

o Obtain the tokenList?o if the # of tokens in the tokenList < 3, Stop and throw an exception,

using class ArithmeticException

o Iterate through the token list?? if the current token is an operand, convert it to type double and

push onto the stack.?? if the current token is an operator:

if the size of the stack is >=2,?o pop a value from the stack into operand2, and

pop a second value from the stack into operand1 o Evaluate the subexpression.. calling

evaluateSubExpression?o push the result back onto the stack

else?o Stop and throw an exception, using class

ArithmeticException

o When done (you are at the end of the token list):?o if ONE value remains on the stack, pop and return the value?o else Stop and throw an exception, using class ArithmeticException