Data Structures, Algorithms, & Applications in Java
Chapter 12, Exercise 41

The infix expression is assumed to be given as a String. Every character in the infix string is assumed to be either one of the permissible operators, one of the permissible delimiters, or an operand. The conversion is done using a stack and scanning the infix form from right to left. The prefix form is also generated from right to left. Right parentheses and operators will be stacked. So, we need priorities for a ")" rather than for a "(". We use 0 as the instack priority of a ")" and 3 for its out of stack priority.

When an operand is encountered, the operand is placed into the prefix form that is being generated (note that the order of operands in the infix and prefix forms is the same; only the positioning of the operators differ).

When an operator is encountered it must be pushed on to the stack, because its left operand is yet to be seen. However, we must first decide whether some operators on the stack must be popped first. Operators at the top of the stack that have an instack priority that is greater than the outstack priority of the newly encountered operator are to be popped.

Right parentheses get stacked when encountered; they do not cause any item to be popped from the stack. A "(" parenthesis results in the popping (and transmittal to the prefix form) of items at the stak top until we encounter the first ")". The encountered ")" is discared.

The code is given below. 
public class ConvertInfixToPrefix
{
   /* An instance of this class is pushed onto the stack.
      Along with the character, the in-stack 
      priority is stored. */
   public static class OperatorData
   {
      public String element;
      public int insidePriority;

      public OperatorData(String element, int insidePriority)
      {
         this.element = element;
         this.insidePriority = insidePriority;
      }
   }

   // contains all legal operators 
   static final String OPERATORS = ")*/+-";
   static final int[] INSTACKPRIORITY = {0, 2, 2, 1, 1};
   static final int[] OUTSTACKPRIORITY = {3, 2, 2, 1, 1};

   public static String convertInfixToPrefix(String infixForm)
   {
      ArrayStack stack = new ArrayStack(); 
                 
      // used to match priorities of operators
      ArrayStack stringValue = new ArrayStack(); 

      // stores the prefix expresion
      StringBuffer stringBuffer = new StringBuffer();

      // '#' with priority 0 is pushed onto the stack
      stack.push(new OperatorData("#", 0));

      // processes the ith character of the string
      for (int i=infixForm.length()-1; i>=0; i--)
      {
         // the current character is processed
         String currentChar = infixForm.substring(i,i+1);

         int operatorCheck = OPERATORS.indexOf(currentChar);

         if (operatorCheck != -1)
         // checks for operator
         {
            int insidePriority = INSTACKPRIORITY[operatorCheck];
            int outsidePriority = OUTSTACKPRIORITY[operatorCheck];

            while (((OperatorData)stack.peek()).insidePriority 
                                  > outsidePriority)            
               stringValue.push(((OperatorData)stack.pop()).element); 

            stack.push(new OperatorData(currentChar, insidePriority));
         }  
         
         else if (currentChar.equals("("))
         {
            while ((((OperatorData)stack.peek()).element)
                                         .equals(")") == false)
            // pops elements till ")" is reached.
               stringValue.push(((OperatorData)stack.pop()).element);
  
          // pops ")"
          stack.pop();
         }
 
         else
            stringValue.push(currentChar);
      } 

      while (!(stack.empty()))
            stringValue.push(((OperatorData)stack.pop()).element);

      while (!(stringValue.empty()))
      // pops elements from stack to create prefix expression
            stringBuffer.append((String)stringValue.pop());

      // returns prefix form, leaving out the '#'
      return (stringBuffer.toString()).substring
                                      (1 , stringBuffer.length());
   }  
}