import java.util.Scanner;


public class ExpressionTree {

    private static class Node{

        private Node left;
        private Node right;
        private Object item;
        private boolean isLeaf;

        private Node(boolean isLeaf, Object item)
        {
            this.item = item;
            this.isLeaf = isLeaf;
            this.left = null;   //Start empty
            this.right = null;
        }
    }

    Node root = null;

    public ExpressionTree (String input)
    {  root = build(input);  }


    private Node build(Scanner input) {
          boolean  leaf;
          String   token;
          double   value;
          Node node;

          leaf = input.hasNextDouble();
          if ( leaf )
          {
             value = input.nextDouble();
             node = new Node ( leaf, value );
          }
          else
          {
             token = input.next();
             node  = new Node ( leaf, token.charAt(0));
             node.left  = build ( input );
             node.right = build ( input );
          }
          return node;
    }

    public void insert(Object item) {
        if(root == null)
            root = new Node(item);

        Node runner = root;

        if (value < node.value) {
            if (node.left != null) {
                insert(node.left, value);
            } else {
                System.out.println("  Inserted " + value +
                                " to left of node " + node.value);
                node.left = new Node(value);
            }
        } else if (value > node.value) {
            if (node.right != null) {
                insert(node.right, value);
            } else {
                System.out.println("  Inserted " + value + "
                to right of node " + node.value);
                node.right = new Node(value);
            }
        }
    }

      public double evaluate ()
       {  return root == null ? 0.0 : evaluate ( root ) ;  }

       // Evaluate the expression:  for internal nodes, this amounts
       // to a post-order traversal, in which the processing is doing
       // the actual arithmetic.  For leaf nodes, it is simply the
       // value of the node.
       private double evaluate ( Node node )
       {
          double result;    // Value to be returned

          if ( node.isLeaf )        // Just get the value of the leaf
             result = Double.valueOf(node.item.toString());
          else
          {
             // We've got work to do, evaluating the expression
             double left, right;
             char   operator = node.item.toString().charAt(0);

             // Capture the values of the left and right subexpressions
             left  = evaluate ( node.left );
             right = evaluate ( node.right );

             // Do the arithmetic, based on the operator
             switch ( operator )
             {
                case '-':  result = left - right;  break;
                case '*':  result = left * right;  break;
                case '/':  result = left / right;  break;
                case '^':  result = Math.pow (left, right );  break;
             // NOTE:  allow fall-through from default to case '+'
                default:   System.out.println ("Unrecognized operator " +
                              operator + " treated as +.");
                case '+':  result = left + right;  break;
             }
          }
          // Return either the leaf's value or the one we just calculated.
          return result;
       }
}