/**
 * @author		David Richardson <richardson-d@iam.uwinnipeg.ca>
 * @version		2011.0203
 * @since 		1.6
 */
public class Problem2
{
	/**
	 * main() is a driver method for the Expression class.
	 *
	 * This method goes through the creation, and displaying of
	 * Expression objects in postfix and infix forms
	 */
	public static void main (String [] args)
	{
		System.out.println("ACS2947: Assignment 1 by David Richardson");
		long startTime = System.currentTimeMillis();
 
		/**
		 * When creating an Expression object, you could also use a single
		 * object and change the expression with *.getInfix(str) and then
		 * update the postfix expression with *.convertToPostfix()
		 */
		Expression [] expr = {
								new Expression ("A+B-C"),
								new Expression ("(A+B)*C"),
								new Expression ("(A+B)*(C-D)"),
								new Expression ("A+((B+C)*(E-F)-G)/(H-I)"),
								new Expression ("A+B*(C+D)-E/F*G+H")
							 };
 
		for(int i = 0; i < expr.length; i++)
		{
			System.out.println("\nInfix Expression: \t" + expr[i].showInfix());
			System.out.println("Postfix Expression: \t" + expr[i].showPostfix());
		}
 
		long elapsedTime = System.currentTimeMillis() - startTime;
		System.out.println("\nProgram Finished in " + elapsedTime + "ms. ");
	}//end main()
}//end class Problem2
 
/**
 * @author		David Richardson <richardson-d@iam.uwinnipeg.ca>
 * @version		2011.0203
 * @since 		1.6
 */
import java.util.Stack;
 
 
public class Expression
{
	private String 	  infix = "";			//The infix form of the expression
	private String 	postfix = "";		  //The postfix form of the expression
 
	/**
	 * Constructors
	 * 	Expression() - An empty constructor, this will create an object without
	 *		storing anything in the infix/postfix values. These values will
	 *		need to be set later with .getInfix() and .convertToPostfix().
	 *
	 *	Expression(String) - This constructor receives a expression in infix
	 *		format and then calls the convertToPostfix method, this storing
	 *		values in both infix and postfix variables.
	 *
	 *		@param String str - An infix expression passed as a string
	 */
	public Expression()
	{
		//empty
	}
 
	public Expression(String str)
	{
		getInfix(str);
	}
 
	/**
	 * getInfix(String) - Method stores a value in the infix variable, and
	 * calls the convertToPostfix() method.
	 *
	 * @param String infix - An infix expression passed as a string.
	 */
	public void getInfix(String infix)
	{
		this.infix = infix;
		convertToPostfix(); //Could be commented out
	}
 
	/**
	 * showInfix() - An accessor method to return the contents of the infix
	 * string.
	 */
	public String showInfix()
	{
		return infix.toString();
	}
 
	/**
	 * showPostfix() - An accessor method to return the contents of the
	 * 	postfix string.
	 */
	public String showPostfix()
	{
		return postfix.toString();
	}
 
	/**
	 * convertToPostfix() - Converts an expression from infix to postfix
	 *
	 * Uses a stack based algorithm to change the infix expression to
	 * it's postfix equivilant.
	 */
	protected void convertToPostfix()
	{
		final String operators = "+-*/";				//Valid Operations
		Stack<Character> pfx = new Stack<Character> ();	//Temp. Stack Storage
		String postfix = "";							//Temp. Postfix Expr.
 
		/**
		 * The following for loop will cycle through every symbol in the infix
		 * expression, and based on the current symbol it will create a postfix
		 * expression.
		 */
		for(int i = 0; i < infix.length(); i++)
		{
			char sym = infix.charAt(i);		//Current Symbol being read.
 
			/**
			 * If sym is an operand (a value) as opposed to an operator
			 */
			if(operators.indexOf(sym) < 0)
			{
				if( sym == '(' )
				{
					pfx.push(sym);
				}//end if
 
				/**
				 * This marks the end of an sub statement, it will pop
				 * off all symbols stored up until a "(" (start of sub
				 * statement) and then append them to the postfix string
				 */
				else if( sym == ')' )
				{
					while( pfx.peek() != '(' )
					{
						postfix += pfx.pop();
					}
 
					pfx.pop();
				}//end else-if
 
				else
				{
					postfix += sym;
				}//end else
			}//end if
 
			/**
			 * If sym is an operator (listed above in "operators")
			 */
			if(operators.indexOf(sym) >= 0)	//sym is an operator
			{
				/**
				 * The following code gets placed in a try catch statement
				 * because wheen using .peek() it's possible to throw an
				 * EmptyStackException, which if not caught, will crash.
				 */
				try
				{
					/**
					 * The while loop cycles through all operators in the
					 * stack back to the last opening parenthesis or until
					 * the stack is empty, whichever comes first. It places
					 * the value on the top of the stack in the postfix string
					 * by popping it off the stack.
					 */
					while( pfx.peek() != '(' && !pfx.empty() )
					{
						if(precedence(pfx.peek(), sym))
						{
							postfix += pfx.pop();
						}//end if
 
						/**
						 * The else statement here is executed so that the
						 * objects in the stack do not take precedence, this
						 * prevents an infinite loop.
						 */
						else
						{
							break;
						}//end else
					}//end while
				}//end try
 
				/**
				 * This catch statement should never be executed, but if the
				 * program is crashing then you can uncomment the println to
				 * debug any errors you may be having.
				 */
				catch ( Exception e)
				{
					//System.out.println(e);
				}//end catch
 
				pfx.push(sym);	//Pushes the current sym onto the stack.
			}//end if
		}//end for
 
		/**
		 * The following while statement gets executed after all symbols
		 * from the infix expression have been loaded and sorted. It clears
		 * out any remaining characters (operators) from the stack, and
		 * appends them to the end of the postfix expression.
		 */
		while( !pfx.empty() )
		{
			postfix += pfx.pop();
		}//end while
 
		this.postfix = postfix;		//Stores the postfix expr in the class var
	}//end convertToPostfix()
 
	/**
	* precedence(char, char) - returns true if the precendence of the first
	* operator is greater than the precedence of the second operator.
	*
	* @param operA - char representation of a binary operator.
	* 		 operB - char representation of another binary operator.
	*
	* @return true: If operA precendence > operB.
	*		  false: otherwise.
	*/
	private static boolean precedence(char operA, char operB)
	{
		boolean isGreater = true;
 
		if(operB == '*' || operB == '/' && operA == '+' || operA == '-')
		{
			isGreater = false;
		}//end if
 
		return isGreater;
	}//end precedence(char, char)
}//end Expression class