Stack.java

import java.util.*;

/**
 * A LIFO stack of generic <CODE>Object</CODE>s.
 *
 * @author Jim Glenn
 * @version 0.1 12/05/2005
 */

public class Stack
{
    /**
     * The list that holds the elements on this stack.  The end of the
     * list is the top of the stack.
     */

    private List elements;

    /**
     * Creates an empty stack.
     */

    public Stack()
    {
	elements = new ArrayList();
    }

    /**
     * Adds an item to the top of this stack.
     *
     * @param toAdd the item to add
     */

    public void push(Object toAdd)
    {
	elements.add(toAdd);
    }

    /**
     * Removes the item at the top of this stack.
     *
     * @return the item at the top of this stack
     */

    public Object pop()
    {
	return elements.remove(elements.size() - 1);
    }

    /**
     * Returns the item at the top of this stack.  That item is not
     * removed.
     *
     * @return the item at the top of this stack
     */

    public Object peek()
    {
	return elements.get(elements.size() - 1);
    }

    /**
     * Returns the number of elements on this stack.
     *
     * @return the size of this stack
     */

    public int size()
    {
	return elements.size();
    }
}

Queue.java

import java.util.*;

/**
 * A FIFO queue of generic <CODE>Object</CODE>s.
 *
 * @author Jim Glenn
 * @version 0.1 12/05/2005
 */

public class Queue
{
    /**
     * The list that holds the elements on this queue.  The front of the
     * list is the front of the queue.
     */

    private List elements;

    /**
     * Creates an empty queue.
     */

    public Queue()
    {
	elements = new LinkedList();
    }

    /**
     * Adds an item to the end of this queue.
     *
     * @param toAdd the item to add
     */

    public void enqueue(Object toAdd)
    {
	elements.add(toAdd);
    }

    /**
     * Removes the item at the front of this queue.
     *
     * @return the item at the front of this queue
     */

    public Object dequeue()
    {
	return elements.remove(0);
    }

    /**
     * Returns the item at the front of this queue.  That item is not
     * removed.
     *
     * @return the item at the front of this queue
     */

    public Object first()
    {
	return elements.get(0);
    }

    /**
     * Returns the number of elements on this queue.
     *
     * @return the size of this queue
     */

    public int size()
    {
	return elements.size();
    }
}

Postfix.java

import java.util.*;
import java.io.*;

/**
 * An arithmetic expression in postfix form.
 *
 * @author Jim Glenn
 * @version 0.2 12/05/2005
 * @version 0.1 11/22/2004
 */

public class Postfix
{
    private String exp;

    /**
     * Creates a postfix expression from the given prefix expression.
     * This version does not handle errors and does not allow
     * integer literals.
     *
     * @param infix a legal infix expression
     */

    public Postfix(String infix)
    {
	exp = "";

	// create a queue containing the tokens in the infix expression;
	// we do this because StringTokenizer has no equivalent of peek

	Queue queue = new Queue();
	StringTokenizer tok = new StringTokenizer(infix);
	while (tok.hasMoreTokens())
	    queue.enqueue(tok.nextToken());

	// create the operator stack

	Stack stack = new Stack();

	while (stack.size() + queue.size() > 0)
	    {
		if (queue.size() == 0)
		    exp = exp + stack.pop() + " ";
		else if (isIdentifier((String)(queue.first())))
		    exp = exp + queue.dequeue() + " ";
		else if (queue.first().equals("("))
		    stack.push(queue.dequeue());
		else if (stack.size() == 0)
		    stack.push(queue.dequeue());
		else if (getPrecedence((String)(queue.first()))
			 > getPrecedence((String)(stack.peek())))
		    stack.push(queue.dequeue());
		else if (stack.peek().equals("(")
			 && queue.first().equals(")"))
		    {
			stack.pop();
			queue.dequeue();
		    }
		else
		    exp = exp + stack.pop() + " ";
	    }
    }

    /**
     * Precedence levels for arithmetic operators and parentheses.
     * Levels are spaced out to make it easier to add operators with
     * in between precedences.
     */

    private static final int ADDITIVE = 0;
    private static final int MULTIPLICATIVE = 10;
    private static final int PARENTHESES = -10;

    /**
     * Returns the precedence of the given operator.
     *
     * @param op an operator or parenthesis
     * @return the precedence of the given operator.
     */

    private static int getPrecedence(String op)
    {
	if (op.equals("+") || op.equals("-"))
	    return ADDITIVE;
	else if (op.equals("*") || op.equals("/"))
	    return MULTIPLICATIVE;
	else if (op.equals("(") || op.equals(")"))
	    return PARENTHESES;
	else
	    throw new IllegalArgumentException();
    }    

    /**
     * Determines if the given string is an identifier.
     *
     * @param id a string
     * @return true iff the given string is an identifier
     */

    private static boolean isIdentifier(String id)
    {
	return Character.isJavaIdentifierStart(id.charAt(0));
    }

    /**
     * Returns a string representation of this expression.
     *
     * @return a string representation of this expression.
     */

    public String toString()
    {
	return exp;
    }

    public static void main(String[] args) throws IOException
    {
	BufferedReader in
	    = new BufferedReader(new InputStreamReader(System.in));

	System.out.println("Enter a legal infix expression:");
	System.out.println(new Postfix(in.readLine()));
    }
}