Class PostfixExpression

java.lang.Object
  |
  +--PostfixExpression

Direct Known Subclasses:

ArithmeticEquation

public abstract class PostfixExpression

extends java.lang.Object

implements Equation

Represents a postfix equation. Equations are commonly of one of three types: infix, postfix, or prefix. The different types have to do with the placement of the operators in relation to the operands. In infix, X + Y, the operator + is in between the operands that it operates on X and Y. In prefix, + X Y, the operator + preceedes the operands X and Y. In postfix, which this class represents, in X Y + the operator + postcedes the operators X and Y. So, + X Y (prefix) is the same as X + Y (infix) is the same as X Y + (postfix).

Postfix notation, unlike infix does not use any grouping symbols. Any equation may be represented because also unlike infix notation there is no order of operations; an operation is preformed when it is reached.

For more information on postfix equations, specifically how to solve them, see the documentation for the solution() method.

Field Summary

protected ExpressionElementStack	expression Stack representing a postfix equation.
protected boolean	TESTING flag which toggles a set of dumps of the different stacks.

Constructor Summary

protected

PostfixExpression() This constructor does nothing whatsoever.

Method Summary

java.lang.String	infixEquation()
void	setEquation(ExpressionElementStack infixExpression) This method sets the content of the expression.
int	solution() This method returns the solution for the equation.
java.lang.String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

expression

protected ExpressionElementStack expression

Stack representing a postfix equation. The top element is the beginning of the equation.

TESTING

protected boolean TESTING

flag which toggles a set of dumps of the different stacks. This information can be used for debugging. The dumps go to java.lang.System#out.

Constructor Detail

PostfixExpression

protected PostfixExpression()

This constructor does nothing whatsoever. It is necessary so that subclasses may call it, the class will not function however unless the subclass generates an ExpressionElementStack and calls setEquation(ExpressionElementStack).

Method Detail

setEquation

public void setEquation(ExpressionElementStack infixExpression)

This method sets the content of the expression. The algorithm used to translate an infix expression (which the ExpressionElementStack infixExpression represents) to a postfix one is this: (for an explanation of the difference between infix and postfix see the introduction to this class.)

• input stack SI which is a stack of ExpressionElements representing an infix equation
• create a new ExpressionElementStack SP representing the new postfix expression.
• Create a new ExpressionElementStack SO to hold operators temporarily
• while SI is not empty
  • if the top of SI is an operator
    • while SO is not empty and the top of SO is of equal or higher precedence than the top of SI
      • pop SO and place the operator on SP
    • pop SI and place the operator on SO
  • else if the top of SI is a gropuping symbol
    • if the top of SI is an opening symbol
      • pop SI and push the grouping symbol on SO
    • else
      • while SO is not empty and the top of SO is not the closing symbol for the top of SI
      • pop SO and place the operator on SP
      • pop SI and throw away the closing symbol
  • else
    • pop SI and place the variable or value in SP
• while SO is not empty
• pop SO and push the operator on SP

SP now contains the expression elements in the proper order for a postfix version of SI
For information on how an infix expression stack is generated see ArithmeticEquation.ArithmeticEquation(java.lang.String).
For information about how a postfix expression is solved by a computer see the solution() method of this class.

Parameters:

infixExpression - stack representing an infix expression

solution

public int solution()

This method returns the solution for the equation. The method that it used to compute the solution is this:

• input the expression (in this case, the expression is an Enumeration of ExpressionElementStack expression;) called SI
• begin a new temporary ExpressionElementStack to hold the work on the solution; called SO
• while the input stack (SI) has more elements
• if the top of SI is a Variable
• pop SI
• find the value for the variable
• push that value on SO
• else if the top of SI is a java.lang.Integer
• pop SI
• push that value on SO
• else if the top of SI is an Operator
• pop SI
• pop SO enough times to get the number of operands needed to allow the operator taken off of SI to process
• operate on the operands popped
• push the solution on SO

Once this code is through processing then SO should contain a single value which is equal to the solution to the expression. If there is more than one value or if at any time an attempt is made to pop an empty stack then there was an error in the format of the equation.

The function currently returns 0 in the case of an error though soon it will throw an InvalidExpressionException.

Specified by:

solution in interface Equation

Returns:

the integer solution to the postfix expression

infixEquation

public java.lang.String infixEquation()

Returns:

a string representing the infix form of the postfix equation

toString

public java.lang.String toString()

Specified by:

toString in interface Equation

Returns:

a string representing the infix form of the postfix equation

Overrides:

toString in class java.lang.Object