import java.util.*;

/** Translates an infix expression to a postfix expression.
 *  @author Koffman and Wolfgang
 * */

public class InfixToPostfix {

  // Nested Class
  /** Class to report a syntax error. */
  public static class SyntaxErrorException
      extends Exception {
    /** Construct a SyntaxErrorException with the specified
        message.
        @param message The message
     */
    SyntaxErrorException(String message) {
      super(message);
    }
  }

  // Data Fields
  /** The operator stack */
  private ArrayStack operatorStack;
  /** The operators */
  private static final String OPERATORS = "+-*/";
  /** The precedence of the operators, matches order in OPERATORS. */
  private static final int[] PRECEDENCE = {
      1, 1, 2, 2};
  /** The postfix string */
  private StringBuffer postfix;

  /** Convert a string from infix to postfix.
      @param expression The infix expression
      @throws SyntaxErrorException
   */
  public String convert(String infix) throws SyntaxErrorException {
    operatorStack = new ArrayStack();
    postfix = new StringBuffer();
    StringTokenizer infixTokens = new StringTokenizer(infix);
    try {
      // Process each token in the infix string.
      while (infixTokens.hasMoreTokens()) {
        String nextToken = infixTokens.nextToken();
        char firstChar = nextToken.charAt(0);
        // Is it an operand?
        if (Character.isJavaIdentifierStart(firstChar)
            || Character.isDigit(firstChar)) {
          postfix.append(nextToken);
          postfix.append(' ');
        } // Is it an operator?
        else if (isOperator(firstChar)) {
          processOperator(firstChar);
        }
        else {
          throw new SyntaxErrorException
              ("Unexpected Character Encountered: "
               + firstChar);
        }
      } // End while.

      // Pop any remaining operators and append them to postfix.
      while (!operatorStack.empty()) {
        Character op = (Character) operatorStack.pop();
        postfix.append(op);
        postfix.append(' ');
      }
      // assert: Stack is empty, return result.
      return postfix.toString();
    }
    catch (EmptyStackException ex) {
      throw new SyntaxErrorException
          ("Syntax Error: The stack is empty");
    }
  }

  /** Method to process operators.
      @param op The operator
      @throws EmptyStackException
   */
  private void processOperator(char op) {
    if (operatorStack.empty()) {
      operatorStack.push(new Character(op));
    }
    else {
      // Peek the operator stack and let topOp be top operator.
      char topOp =
          ( (Character) operatorStack.peek()).charValue();
      if (precedence(op) > precedence(topOp)) {
        operatorStack.push(new Character(op));
      }
      else {
        // Pop all stacked operators with equal or higher precedence than op.
        while (!operatorStack.empty()
               && precedence(op) <= precedence(topOp)) {
          operatorStack.pop();
          postfix.append(topOp);
          postfix.append(' ');
          if (!operatorStack.empty()) {
            // Reset topOp.
            topOp = ( (Character)
                     operatorStack.peek()).charValue();
          }
        } 
        operatorStack.push(new Character(op));
      }
    }
  }

  /** Determine whether a character is an operator.
      @param ch The character to be tested
      @return true if ch is an operator
   */
  private boolean isOperator(char ch) {
    return OPERATORS.indexOf(ch) != -1;
  }

  /** Determine the precedence of an operator.
      @param op The operator
      @return the precedence
   */
  private int precedence(char op) {
    return PRECEDENCE[OPERATORS.indexOf(op)];
  }
}