/** Convert.java -- convert infix to postfix.
 */
import java.io.*;
import java.util.*;

public class Convert
{
  public static void main(String [] args) throws IOException
  {
    BufferedReader kbd = new BufferedReader(new InputStreamReader(System.in));
    System.out.print("Please enter an infix expression:  ");
    String line = kbd.readLine();
    System.out.println("You entered " + line);
    StringTokenizer tok = new StringTokenizer(line, " ");
    LinkedListStack stack = new LinkedListStack();
    String postfix = "";

    while (tok.hasMoreTokens())
    {
      String token = tok.nextToken();

      // If the token is an operand, append it to the postfix expression.
      // This is because the order of the operands doesn't change, and the
      // operators will be appended later.
      char firstChar = token.charAt(0);
      if (firstChar >= '0' && firstChar <= '9' || firstChar == '.')
	postfix += token + " ";

      // push open parentheses
      else if (token.equals("("))
	stack.push(token);

      // When we encounter a ')', we need to pop operators off the stack until
      // we see the corresponding '('.  The operators will then be in the
      // appropriate order in the postfix output.  We break from the loop on
      // seeing the '(' so we can avoid appending it to the output.
      else if (token.equals(")"))
      {
	String operator;
        while (true)
        {
          operator = (String) stack.pop();
          if (operator.equals("("))
	    break;
          postfix += operator + " "; 
	}
      }

      // The last case handles all the operators, + - * /
      // If the stack is empty, push this operand on the stack.
      // If the stack is not empty, pop operators of >= precedence for output,
      //   stopping when we encounter a '(' or an operator of lower precedence,
      //   or the stack becomes empty.  Finally, push this operator on stack.
      //   (for = precedence we pop because of left-to-right associativity.)
      else
      {
	if (stack.size() == 0)
	  stack.push(token);
	else 
        {
          while (true)
	  {
	    if (stack.size() == 0)
	      break;
	    String topOfStack = (String) stack.peek();
	    if (topOfStack.equals("(") ||
	        lowerPrecedence(topOfStack.charAt(0), 
				token.charAt(0)))
	      break;
	    else
	      postfix += stack.pop() + " ";
	  }
	  stack.push(token);
	}
      }
    }

    // When we run out of input, empty (pop) the stack onto output.
    while(stack.size() > 0)
      postfix += stack.pop() + " ";


    System.out.println("The postfix version of the expression is " + postfix);
  }

  // A method to determine if one operator is of lower precedence.
  // The only case where we return true is when the first operand is strictly
  // lower precedence, which encompasses the cases of op1 = + or - and
  // op2 = * or /.  
  public static boolean lowerPrecedence(char op1, char op2)
  {
    if ((op1 == '+' || op1 == '-') && (op2 == '*' || op2 == '/'))
      return true;
    else
      return false;
  }
}