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

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

The logic behind the codes for the various methods is described in the solutions to Exercises 36 - 43.

The code is given below. 
public class Expression extends LinkedBinaryTree
{
   static String OPERATORS = "+*-/";
   static ArrayStack stack = new ArrayStack();

   // outputs the fully parenthesised infix form of the expression tree.
   public void expressionTreeToInfix()
   {
      BinaryTreeNode root = (BinaryTreeNode)this.root;
      expressionTreeToInfix(root);
   }

   private void expressionTreeToInfix(BinaryTreeNode t)
   {
      if (t != null)
      {
         // left child
         System.out.print("(");
         expressionTreeToInfix(t.leftChild);         

         // visit current node
         System.out.print((String)t.element);
            
         // right child
         expressionTreeToInfix(t.rightChild);
         System.out.print(")");
      }    
   }


   // outputs the prefix form of the expression tree.
   public void prefixOutput()
   {
      BinaryTreeNode root = (BinaryTreeNode)(this.root);
      BinaryTreeTraversal.preOrder(root);
   }

   // outputs the postfix form of the expression tree.
   public void postfixOutput()
   {
      BinaryTreeNode root = (BinaryTreeNode)(this.root);
      BinaryTreeTraversal.postOrder(root);
   }

   // converts from prefix to binary tree
   public BinaryTreeNode prefixToExpressionTree(String prefixForm)
   {
      return (this.root = PrefixToBinaryTree.prefixToBinaryTree(prefixForm));      
   }

   // converts from postfix to expression tree.
   public BinaryTreeNode postfixToExpressionTree(String postfixForm)
   {
      return (this.root = PostfixToBinaryTree.postfixToBinaryTree(postfixForm));      
   }

   // converts from pinfix to expression tree.
   public BinaryTreeNode infixToExpressionTree(String infixForm)
   {
      return (this.root = InfixToBinaryTree.infixToBinaryTree(infixForm));      
   }

   // evaluates an expression tree.
   public int expressionTreeEvaluation()
   {
      BinaryTreeNode root = (BinaryTreeNode)this.root;

      expressionTreeEvaluation(root);

      return ((Integer)stack.peek()).intValue();
   }

   private void expressionTreeEvaluation(BinaryTreeNode t)
   {


      if (t != null)
      {  
         // current character
         String op = (String)t.element;

         //left child  
         expressionTreeEvaluation(t.leftChild);   

         // right child
         expressionTreeEvaluation(t.rightChild);  

         // check for operator
         int index = OPERATORS.indexOf(op);

         if (index == 0) 
         // handle case when '+' is found
            stack.push(new Integer(((Integer)stack.pop()).intValue() + ((Integer)stack.pop()).intValue())); 
         else if (index == 1) 
         // handle case when '*' is found
            stack.push(new Integer(((Integer)stack.pop()).intValue() * ((Integer)stack.pop()).intValue())); 
         else if (index == 2)
         // handle case when '-' is found
         {
            int rightOperand = ((Integer)stack.pop()).intValue();
            int leftOperand = ((Integer)stack.pop()).intValue();
            stack.push(new Integer(leftOperand - rightOperand));
         }
         else if (index == 3)
         // handle case when '/' is found
         {
          int rightOperand = ((Integer)stack.pop()).intValue();
          int leftOperand = ((Integer)stack.pop()).intValue();
          stack.push(new Integer(leftOperand / rightOperand));
         }
         else if (index == -1)
         // operand
         {
            stack.push(Integer.valueOf(op));
         }
      }
   } 
}