freegraph
Class ExpressionStack

java.lang.Object
  |
  +--java.util.AbstractCollection
        |
        +--java.util.AbstractList
              |
              +--java.util.Vector
                    |
                    +--java.util.Stack
                          |
                          +--freegraph.ExpressionStack

All Implemented Interfaces:

java.lang.Cloneable, java.util.Collection, java.util.List, java.util.RandomAccess, java.io.Serializable

public class ExpressionStack

extends java.util.Stack

ExpressionStack converts a free-form Infix expression into Postfix, or Reverse Polish Notation (RPN). The expression is parsed into tokens, and converted to RPN using a standard stack technique. After converted to RPN, the expression is on a stack which can be easily evaluated using ExpressionEvaluator.

The stack technique involves using 3 stacks, an infix stack, a hold stack, and an RPN stack. Following a algorithm, items on the infix stack are tested, and based on what is on the top of the HOLD stack, one of 5 "ACTION" constants are followed. The ExpressionItem.getAction() method is called on the ExpressionItem on the top of the infix stack to determine which action to take.

When the InfixExpression property is set, the expression is parsed, and the RPN stack is immediately available.

The algorithm used is from: Tanenbaum, Andrew S. 1990. Structured Computer Organization, 3rd ed., New Jersey: Prentice Hall. (pp. 268-272)

See Also:

ExpressionEvaluator, Serialized Form

Field Summary

static int	ACTION_COMPLETE Action indicating that conversion is complete
static int	ACTION_DELETE_HOLD Action indicating that the top of the hold stack should be deleted
static int	ACTION_ERROR Action indicating that an error has occured because an unexpected token was encountered
static int	ACTION_HOLD_TO_RPN_STACK Action indicating that the top of the hold stack should be put on the top of the RPN stack
static int	ACTION_INFIX_TO_HOLD_STACK Action indicating that the top of the infix stack should be put on the top of the hold stack
static int	ACTION_INFIX_TO_RPN_STACK Action indicating that the top of the infix stack should be put on the top of the RPN stack

Fields inherited from class java.util.Vector

capacityIncrement, elementCount, elementData

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

ExpressionStack()
Constructs a new ExpressionStack which initially has no infixExpression

ExpressionStack(java.lang.String infixExpression)
Constructs a new ExpressionStack for the infixExpression.

Method Summary

java.lang.String	getInfixExpression()
void	setInfixExpression(java.lang.String infixExpression) sets the infix expression for the stack.

Methods inherited from class java.util.Stack

empty, peek, pop, push, search

Methods inherited from class java.util.Vector

add, add, addAll, addAll, addElement, capacity, clear, clone, contains, containsAll, copyInto, elementAt, elements, ensureCapacity, equals, firstElement, get, hashCode, indexOf, indexOf, insertElementAt, isEmpty, lastElement, lastIndexOf, lastIndexOf, remove, remove, removeAll, removeAllElements, removeElement, removeElementAt, removeRange, retainAll, set, setElementAt, setSize, size, subList, toArray, toArray, toString, trimToSize

Methods inherited from class java.util.AbstractList

iterator, listIterator, listIterator

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.List

iterator, listIterator, listIterator

Field Detail

ACTION_INFIX_TO_RPN_STACK

public static final int ACTION_INFIX_TO_RPN_STACK

Action indicating that the top of the infix stack should be put on the top of the RPN stack

See Also:

Constant Field Values

ACTION_INFIX_TO_HOLD_STACK

public static final int ACTION_INFIX_TO_HOLD_STACK

Action indicating that the top of the infix stack should be put on the top of the hold stack

See Also:

Constant Field Values

ACTION_HOLD_TO_RPN_STACK

public static final int ACTION_HOLD_TO_RPN_STACK

Action indicating that the top of the hold stack should be put on the top of the RPN stack

See Also:

Constant Field Values

ACTION_DELETE_HOLD

public static final int ACTION_DELETE_HOLD

Action indicating that the top of the hold stack should be deleted

See Also:

Constant Field Values

ACTION_COMPLETE

public static final int ACTION_COMPLETE

Action indicating that conversion is complete

See Also:

Constant Field Values

ACTION_ERROR

public static final int ACTION_ERROR

Action indicating that an error has occured because an unexpected token was encountered

See Also:

Constant Field Values

Constructor Detail

ExpressionStack

public ExpressionStack(java.lang.String infixExpression)
                throws ExpressionException

Constructs a new ExpressionStack for the infixExpression.

Parameters:

infixExpression - a free-form infix expression

ExpressionStack

public ExpressionStack()

Constructs a new ExpressionStack which initially has no infixExpression

Method Detail

setInfixExpression

public void setInfixExpression(java.lang.String infixExpression)
                        throws ExpressionException

sets the infix expression for the stack. The expression is converted to postfix and is available through the stack.

ExpressionException

getInfixExpression

public java.lang.String getInfixExpression()