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

We assume that each operand is a single character and that the operators in the prefix form are limited to the following set:
+ (addition, binary)
- (subtraction, binary)
* (multiplication, binary)
/ (division, binary)
! (addition, unary)
? (subtraction, unary)

The prefix form is assumed to be given as a String. Every character in the prefix string is assumed to be either a binary operator, a unary operator, or an operand. The conversion is done using a stack and scanning the prefix form from right to left. When an operand is encountered, the operand is placed into a binary tree node and this node is pushed on the stack. When a binary operator is encountered, the binary operator is put into a binary tree node, its two operands are popped from the stack and made the left and right subtree of the operator node. The operator node is then pushed on to the stack. When a unary operator is encountered, the unary operator is put into a binary tree node, its single operand is popped from the stack and made the right subtree of the operator node. The operator node is then pushed on to the stack. When done, the stack contains the root of the constructed binary tree.

The code is given below. 

public class PrefixToBinaryTree
{
   // legal binary and unary operators
   static final String BINARYOPS = "+-*/";
   static final String UNARYOPS = "!?";

   public static BinaryTreeNode prefixToBinaryTree(String exp)
   {
      ArrayStack stack = new ArrayStack();
      
      // Process exp from right to left one character at a time 
      for (int i = exp.length()-1; i >= 0; i--)
      {// process i'th character of exp
         String currentChar = exp.substring(i,i+1);

         if (BINARYOPS.indexOf(currentChar) != -1)
         {// binary operator;
            BinaryTreeNode currentNode = new BinaryTreeNode(currentChar, 
                                            (BinaryTreeNode)stack.pop(), 
                                            (BinaryTreeNode)stack.pop());
            stack.push(currentNode);
         }
         else if (UNARYOPS.indexOf(currentChar) != -1)
         // unary operator
            stack.push(new BinaryTreeNode(currentChar, null,
                                     (BinaryTreeNode) stack.pop()));
         else
         // operand
            stack.push(new BinaryTreeNode(currentChar));					
         }		

         if (!stack.empty())   
         // root
            return((BinaryTreeNode)stack.peek());
         else
         // empty string is passed as argument
            return null;
   }
}