ParseTree.java

/*************************************************************************
 *  Compilation:  javac ParseTree.java
 *  Execution:    java ParseTree
 *  Dependencies: StdIn.java
 *  
 *  Evaluates a prefix expression by explicitly building the parse
 *  tree and doing a preorder traversal.
 *
 *  % java ParseTree
 *  * + + 4 5 * 6 7 8     // corresponds to (((4+5)+(6*7))*8)
 *  <Ctrl-d>              // use <Ctrl-z> on Windows for EOF
 *  * + + 4 5 * 6 7 8     // preorder traversal of tree
 *  408                   // the answer
 *
 *  Known limitations
 *  -----------------
 *  - The toString method runs is very slow (quadratic time) since it
 *    uses string concatenation instead of a StringBuffer. But this method
 *    is intended for debugging purposes only.
 *
 *************************************************************************/


public class ParseTree {
    private String s;
    private ParseTree left, right;
   
    // creat the parse tree from standard input
    public ParseTree() {
        s = StdIn.readString();
        if (s.equals("+") || s.equals("*")) {
            left  = new ParseTree();
            right = new ParseTree();
        }
    }

    // evaluate the parse tree
    public int eval() {
        if      (s.equals("+")) return left.eval() + right.eval();
        else if (s.equals("*")) return left.eval() * right.eval();
        else                    return Integer.parseInt(s);
    }

    // preorder traversal
    public String toString() {
        if (s.equals("+") || s.equals("*"))
            return s + " " + left + " " + right;
        else
            return s;
    }

    // test out the parse tree
    public static void main(String[] args) {
        ParseTree tree = new ParseTree();
        System.out.println(tree);
        System.out.println(tree.eval());
    }

}