infix2postfix
Class Infix2PostfixConverter

java.lang.Object
  infix2postfix.Infix2PostfixConverter

public class Infix2PostfixConverter

extends java.lang.Object

This object converts infix expression into equivalent postfix expression.

Infix expression is assumed to be having 'space' as a separator between operands and operators and "grouping characters" which are '(' and ')'. If you want any other grouping characters you can extend this class to handle that.

Further, this object can't handle any other infix expression format than string. So if there is a possibility of having Collection of objects that needs be treated as infix expression then this object will not be useful.

Author:

Maulin H. Vasavada

Field Summary

protected static int	GROUP_CLOSE Type identifier for group close symbol that is ')' for this object
static java.lang.String	GROUP_CLOSE_SYMBOL Group Close symbol
protected static int	GROUP_OPEN Type identifier for group open symbol that is '(' for this object
static java.lang.String	GROUP_OPEN_SYMBOL Group Open symbol
private static java.lang.String	INFIX_EXPRESSION_SEPARATOR Infix expression separator
protected static int	INVALID_SYMBOL_TYPE Type identifier for an invalid symbol
static java.lang.String	MINUS_SIGN_POSTFIX_EQUIV Minus sign equivalent to put in postfix as postfix needs to distinguish between binary and unary minus
protected static int	OPERAND Type identifier for an operand
private OperandManager	operandManager Operand Mananger to be used for this conversion
protected static int	OPERATOR Type identifier for an operator
private java.util.HashMap	operators Map of valid operators allowed in this conversion
private static java.lang.String	POSTFIX_EXPRESSION_SEPARATOR Postfix expression separator

Constructor Summary

Infix2PostfixConverter(OperandManager operandManager)
Constructor

Method Summary

boolean	addOperator(Operator operator) Adds an operator to "valid operators" list.
protected void	append(java.lang.StringBuffer postfix, java.lang.String symbol) Append a symbol to postfix output.
protected java.lang.String	getInfixExpressionSeparator() This method returns the separator for the infix expression.
java.util.HashMap	getOperators() Returns copy of "valid operators" list.
java.lang.String	getPostfix(java.lang.String infix) This method converts a given infix into equivalent postfix expression.
protected java.lang.String	getPostfixExpressionSeparator() This method returns the separator for the postfix expression generated by this object.
private int	getPriority(java.lang.String symbol) Returns priority of an operator having specified symbol.
protected int	getSymbolType(java.lang.String symbol) This method returns type identifier for a given symbol.
private boolean	isFunctionOperator(java.lang.String symbol) Verifies if the given symbol is a "function operator".
protected boolean	isGroupCloseSymbol(java.lang.String symbol) This method checks if the given symbol is GROUP CLOSE symbol or not.
protected boolean	isGroupOpenSymbol(java.lang.String symbol) This method checks if the given symbol is GROUP OPEN symbol or not.
protected boolean	isOperand(java.lang.String symbol) Verifies if the given symbol is an allowed operand or not.
protected boolean	isOperator(java.lang.String symbol) Verifies if the given symbol is an allowed operator or not.
protected java.lang.String[]	parse(java.lang.String infix) Tokenize input infix expression based on a separator.
boolean	removeOperator(java.lang.String postfixEquivSymbol) Removes an operator from "valid operators" list.
protected void	setOperandManager(OperandManager operandManager) Sets an operand manager for this coversion.

Methods inherited from class java.lang.Object

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

Field Detail

GROUP_OPEN

protected static final int GROUP_OPEN

Type identifier for group open symbol that is '(' for this object

See Also:

Constant Field Values

GROUP_CLOSE

protected static final int GROUP_CLOSE

Type identifier for group close symbol that is ')' for this object

See Also:

Constant Field Values

OPERATOR

protected static final int OPERATOR

Type identifier for an operator

See Also:

Constant Field Values

OPERAND

protected static final int OPERAND

Type identifier for an operand

See Also:

Constant Field Values

INVALID_SYMBOL_TYPE

protected static final int INVALID_SYMBOL_TYPE

Type identifier for an invalid symbol

See Also:

Constant Field Values

GROUP_OPEN_SYMBOL

public static final java.lang.String GROUP_OPEN_SYMBOL

Group Open symbol

See Also:

Constant Field Values

GROUP_CLOSE_SYMBOL

public static final java.lang.String GROUP_CLOSE_SYMBOL

Group Close symbol

See Also:

Constant Field Values

INFIX_EXPRESSION_SEPARATOR

private static final java.lang.String INFIX_EXPRESSION_SEPARATOR

Infix expression separator

See Also:

Constant Field Values

POSTFIX_EXPRESSION_SEPARATOR

private static final java.lang.String POSTFIX_EXPRESSION_SEPARATOR

Postfix expression separator

See Also:

Constant Field Values

MINUS_SIGN_POSTFIX_EQUIV

public static final java.lang.String MINUS_SIGN_POSTFIX_EQUIV

Minus sign equivalent to put in postfix as postfix needs to distinguish between binary and unary minus

See Also:

Constant Field Values

operandManager

private OperandManager operandManager

Operand Mananger to be used for this conversion

operators

private java.util.HashMap operators

Map of valid operators allowed in this conversion

Constructor Detail

Infix2PostfixConverter

public Infix2PostfixConverter(OperandManager operandManager)

Constructor

Method Detail

addOperator

public boolean addOperator(Operator operator)

Adds an operator to "valid operators" list.

setOperandManager

protected void setOperandManager(OperandManager operandManager)

Sets an operand manager for this coversion.

removeOperator

public boolean removeOperator(java.lang.String postfixEquivSymbol)

Removes an operator from "valid operators" list.

getOperators

public java.util.HashMap getOperators()

Returns copy of "valid operators" list.

getInfixExpressionSeparator

protected java.lang.String getInfixExpressionSeparator()

This method returns the separator for the infix expression. This separator is used for infix expression parsing to tokenize various symbols in the expression.

Default separator is 'space'.

Returns:

java.lang.String Infix separator character for this object

See Also:

getPostfixExpressionSeparator()

getPostfixExpressionSeparator

protected java.lang.String getPostfixExpressionSeparator()

This method returns the separator for the postfix expression generated by this object. This separator is used to generate postfix expression that can be later parsed based on this separator token.

Default separator is 'space'.

Returns:

java.lang.String Postfix separator for this object

See Also:

getInfixExpressionSeparator(), parse(java.lang.String)

getSymbolType

protected int getSymbolType(java.lang.String symbol)

This method returns type identifier for a given symbol.

Parameters:

symbol - A symbol that needs to be categorized into appropriate type. Possible types are,

		    1. GROUP_OPEN
		    2. GROUP_CLOSE
		    3. OPERATOR
		    4. OPERAND
		    

Returns:

int Type of the given symbol

See Also:

GROUP_OPEN, isGroupOpenSymbol(java.lang.String), GROUP_CLOSE, isGroupCloseSymbol(java.lang.String), OPERATOR, isOperator(java.lang.String), OPERAND, isOperand(java.lang.String)

isGroupOpenSymbol

protected boolean isGroupOpenSymbol(java.lang.String symbol)

This method checks if the given symbol is GROUP OPEN symbol or not.

Default implementation considers GROUP_OPEN_SYMBOL variable in this object as allowed GROUP OPEN symbol.

Parameters:

symbol - Symbol to be checked

Returns:

boolean true if the given symbol is GROUP OPEN;false otherwise;

See Also:

GROUP_OPEN_SYMBOL

isGroupCloseSymbol

protected boolean isGroupCloseSymbol(java.lang.String symbol)

This method checks if the given symbol is GROUP CLOSE symbol or not. Default implementation considers GROUP_CLOSE_SYMBOL variable in this object as allowed GROUP CLOSE symbol.

Parameters:

symbol - Symbol to be checked

Returns:

boolean true if the given symbol is GROUP CLOSE;false otherwise;

See Also:

GROUP_CLOSE_SYMBOL

isOperator

protected boolean isOperator(java.lang.String symbol)

Verifies if the given symbol is an allowed operator or not.

If the symbol is in "valid operators" list it is considered to be a symbol.

isOperand

protected boolean isOperand(java.lang.String symbol)

Verifies if the given symbol is an allowed operand or not.

Default implementation returns false if,

 1. isOperator() returns false AND
 2. isGroupOpenSymbol() returns false AND
 3. isGroupCloseSymbol() returns false AND
 4. operand manager's isOperand() returns false 
 

See Also:

isOperator(java.lang.String), isGroupOpenSymbol(java.lang.String), isGroupCloseSymbol(java.lang.String), OperandManager.isOperand(Object)

append

protected void append(java.lang.StringBuffer postfix,
                      java.lang.String symbol)

Append a symbol to postfix output. Default implementation uses 'space' to separate symbols in generated postfix expression.

Parameters:

postfix - StringBuffer storing the current postfix expression

symbol - A symbol that needs to be appended to the current postfix

See Also:

getPostfixExpressionSeparator()

parse

protected java.lang.String[] parse(java.lang.String infix)

Tokenize input infix expression based on a separator. This method uses INFIX_EXPRESSION_SEPARATOR for tokenizing the input infix expression.

It considers tab as a separator as well.

Parameters:

infix - Infix expression to be tokenize

Returns:

java.lang.String[] Tokenized infix expression

getPriority

private int getPriority(java.lang.String symbol)

Returns priority of an operator having specified symbol.

isFunctionOperator

private boolean isFunctionOperator(java.lang.String symbol)

Verifies if the given symbol is a "function operator".

e.g. sin, cos, tan, max, min etc math operators.

getPostfix

public java.lang.String getPostfix(java.lang.String infix)
                            throws InvalidSymbolTypeException

This method converts a given infix into equivalent postfix expression.

Parameters:

infix - Infix expression to be converted into postfix

Returns:

java.lang.String Equivalent postfix expression for the given infix

Throws:

InvalidSymbolTypeException - If the given symbol doesn't satisfy validity criteria for the infix expression used in this convertor