ExprTree.java

Download 
1/*2 * ExprTree.java3 *4 * Computer Science S-22, Harvard University5 */ 6 7import java.util.*;8 9/**10 * ExprTree - a class for representing a binary tree that represents11 * an arithmetic expression involving the operators +, -, *, or /.12 * The terms must be single lower-case letters and the expression must13 * be fully parenthesized, e.g.:14 *15 *      (((a + b) * c) + (d - (e / f)))16 */17public class ExprTree {18    private class Node {19        private char contents;   // either an arithmetic operator or a..z20        private Node left;       // left child21        private Node right;      // right child22        23        /* 24         * isLeaf() - is the specified node a leaf node? 25         */26        private boolean isLeaf() {27            return (left == null && right == null);28        }29    }30    31    private Node root;32    private Scanner in;33    34    public ExprTree() {35        root = null;36        in = new Scanner(System.in);37    }38    39    /**40     * inorderPrint - uses infix notation to print the expression tree.41     * It calls inorderPrintTree to perform a recursive inorder traversal.42     */43    public void inorderPrint() {44        if (root != null) {45            inorderPrintTree(root);46        }47    }48    49    /*50     * inorderPrintTree - uses infix notation to print the (sub)tree51     * with the specified root.  It makes recursive calls to print the52     * left and right subtrees of the specified root.53     */54    private static void inorderPrintTree(Node root) {55        if (root.isLeaf())56            System.out.print(root.contents);57        else {58            // internal node - an operator59            System.out.print("(");60            inorderPrintTree(root.left);61            System.out.print(" " + root.contents + " ");62            inorderPrintTree(root.right);63            System.out.print(")");64        }65    }66    67    /**68     * preorderPrint - uses prefix notation to print the expression tree.69     * It calls preorderPrintTree to perform a recursive preorder traversal.70     */71    public void preorderPrint() {72        if (root != null) {73            preorderPrintTree(root);74        }75    }76    77    /*78     * preorderPrintTree - uses prefix notation to print the79     * expression tree that has the specified node as its root.  It80     * prints the tree by performing a recursive preorder traversal.81     */82    private static void preorderPrintTree(Node root) {83        if (root.isLeaf()) {84            System.out.print(root.contents);85        } else {86            // interior node -- an operator87            // first the node itself (the root of the subtree)88            switch (root.contents) {89                case '+':90                    System.out.print("add"); 91                    break;92                case '-':93                    System.out.print("subtr"); 94                    break;95                case '*':96                    System.out.print("mult"); 97                    break;98                case '/':99                    System.out.print("divide"); 100                    break;101            }102            103            // then the left and right subtrees104            System.out.print("(");105            preorderPrintTree(root.left);106            System.out.print(", ");107            preorderPrintTree(root.right);108            System.out.print(")");109        }110    }111    112    /**113     * postorderPrint - uses postfix notation to print the expression tree.114     * It calls postorderPrintTree to perform a recursive postorder traversal.115     */116    public void postorderPrint() {117        if (root != null) {118            postorderPrintTree(root, 0);119        }120    }121    122    /*123     * postorderPrintTree - uses postfix notation to print the124     * expression tree that has the specified node as its root.  It125     * prints the tree by performing a recursive postorder traversal.126     * The margin argument helps to align the output properly.127     */128    private static void postorderPrintTree(Node root, int margin) {129        if (root.isLeaf()) {130            printMargin(margin);131            System.out.print(root.contents + "  ");132        } else {133            postorderPrintTree(root.left, margin + 1);134            postorderPrintTree(root.right, margin + 1);135            136            printMargin(margin);137            switch (root.contents) {138                case '+':139                    System.out.print("add above"); 140                    break;141                case '-':142                    System.out.print("subtract above"); 143                    break;144                case '*':145                    System.out.print("multiply above"); 146                    break;147                case '/':148                    System.out.print("divide above"); 149                    break;150            }151        }152    }153    154    /**155     * printMargin - used to print leading spaces when outputting156     * expressions in postfix notation157     */158    private static void printMargin(int margin) {159        System.out.println();160        for (int i = 1; i <= margin; i++) {161            System.out.print("    ");162        }163    }164    165    /**166     * readExpression - parses an arithmetic expression entered at the167     * keyboard and builds an expression tree for the expression.  It168     * calls readTree to recursively process the expression.169     */170    public void read() {171        root = readTree();172    }173    174    /*175     * readTree - recursively parses an arithmetic expression obtained176     * from the user and builds a binary tree for the expression.  The177     * root of the tree is returned.178     */179    private Node readTree() {180        Node n = new Node();181        182        // get next non-whitespace char183        char ch = in.findInLine("(\\S)").charAt(0);184        if ((ch >= 'a') && (ch <='z')) {185            // leaf node186            n.contents = ch;187            n.left = null;188            n.right = null;189        } else if (ch == '(') {190            // an expression191            n.left = readTree();192            n.contents = in.findInLine("(\\S)").charAt(0);193            n.right = readTree();194            ch = in.findInLine("(\\S)").charAt(0);195            if (ch != ')') {196                System.out.print("EXPECTED ) - } ASSUMED...");197            }198        } else {199            System.out.print("EXPECTED ( - CAN'T PARSE");200            System.exit(1);201        }202        203        return n;204    }205    206    /*207     * Program to read an arithmetic expression, convert it to a tree, and208     * print the tree in infix, prefix, and postfix notation.209     */210    public static void main(String[] args) {211        // Read in the expression and build the tree.212        System.out.println("\nType a fully parenthesized expression " +213                           "using a..z,+,-,*,/");214        215        ExprTree tree = new ExprTree();216        tree.read();217        218        // Output it using all three types of notation.219        System.out.println("\n* INFIX NOTATION:");220        tree.inorderPrint();221        System.out.print("\n\n* PREFIX NOTATION:\n");222        tree.preorderPrint();223        System.out.print("\n\n* POSTFIX NOTATION:");224        tree.postorderPrint();225        System.out.println();226    }227}