// file PrefixToExpTree.java

// Convert a prefix arithmetic expression to an expression tree.
// Operators: + - x / (Have to use x rather than * because Linux interprets
//   * as a wildcard for filenames).

public class PrefixToExpTree {
   public static int start;

// Check whether String s is a number (on the assumption that anything
// starting with a digit is a number).

   public static boolean isNumber(String s) {
       return ('0' <= s.charAt(0) && s.charAt(0) <= '9');
      }

// Top level method. s is an array with a mixture of Integers and 
// Characters. The method initializes start to 0 and then calls the
// recursive method PrefixToExpTree1.

   public static ExpTree PrefixToExpTree(String[] s) {
       start = 0;
       return PrefixToExpTree1(s);
      }

// read a full prefix expression off s starting at start, and move
// variable "start" up to the beginning of the next expression.

   public static ExpTree PrefixToExpTree1(String[] s) {
       if (start >= s.length) {
            System.out.println("Ill-formed expression");
            return null;
          }
       ExpTree N = null;
       int place = start;
       start++;
       if (isNumber(s[place]))
           N = new Constant(Integer.parseInt(s[place]));
       else  {
         ExpTree[] args = new ExpTree[2];
         args[0] = PrefixToExpTree1(s);
         args[1] = PrefixToExpTree1(s);
         switch(s[place].charAt(0)) {
            case '+': N = new Sum(args); break;
            case 'x': N = new Product(args); break;
            case '-': N = new Subtract(args[0],args[1]); break;
            case '/': N = new Divide(args[0],args[1]); break;
            default: ;
          }
        }
        return N;
    }  // end PrefixToExpTree1 
             

// The "main" method reads a prefix expression from input (symbols separated
// by white space)
// calls PrefixToExpTree to convert it to an expression tree, then evaluates
// and displays it.

   public static void main(String[] args) {
      ExpTree N = PrefixToExpTree(args);
      System.out.println(N.evaluate());
      System.out.println(N.display());
    }

}