Question

Assignment #2 (JAVA)

In assignment 1 you had used the data structure called Stack to evaluate arithmetic expressions by first converting the given infixed expressions to postfixed expressions, and then evaluated the post fixed expression. Repeat the exercise for this assignment (assignment 2) by using the data structure called Binary Trees.

Your output must display the original expression, the postfixed expression representing the Binary tree, and the evaluated result. Please bear in mind that a given expression could result in one of the following:

• Mismatch parentheses
• Too many operators, or too many operands in which case the expression would not have been written properly in the first place
• The result is assumed to be correct Information regarding

Assignment 1 original expression

class RPN {

public static void main(String[] arg) { String s[] = {"5 + ) * ( 2", " 2 + ( - 3 * 5 ) ", "(( 2 + 3 ) * 5 ) * 8 ", "5 * 10 + ( 15 - 20 ) ) - 25", " 5 + ( 5 * 10 + ( 15 - 20 ) - 25 ) * 9" };

for (int i = 0; i < s.length; i++) {

Arithmetic a = new Arithmetic(s[i]);

if (a.isBalance()) { System.out.println("Expression " + s[i] + " is balanced\n");
a.postfixExpression();

System.out.println("The post fixed expression is " + a.getPostfix()); a.evaluateRPN();
a.evaluateRPN();

System.out.println("Result of this expression = "+a.getResult());

}else{

System.out.println("Expression is not balanced\n");

}

}

}

}

Answer 1

public class BinaryTree {
    private class Node {
        private char contents;   // either an arithmetic operator or a..z
        private Node left;       // left child
        private Node right;      // right child
        
        /* 
         * isLeaf() - is the specified node a leaf node? 
         */
        private boolean isLeaf() {
            return (left == null && right == null);
        }
    }
    
    private Node root;
    private Scanner in;
    
    public BinaryTree() {
        root = null;
        in = new Scanner(System.in);
    }

/**
     * postorderPrint - uses postfix notation to print the expression tree.
     * It calls postorderPrintTree to perform a recursive postorder traversal.
     */
    public void postorderPrint() {
        if (root != null) {
            postorderPrintTree(root, 0);
        }
    }
    
    /*
     * postorderPrintTree - uses postfix notation to print the
     * expression tree that has the specified node as its root.  It
     * prints the tree by performing a recursive postorder traversal.
     * The margin argument helps to align the output properly.
     */
    private static void postorderPrintTree(Node root, int margin) {
        if (root.isLeaf()) {
            printMargin(margin);
            System.out.print(root.contents + "  ");
        } else {
            postorderPrintTree(root.left, margin + 1);
            postorderPrintTree(root.right, margin + 1);
            
         }
    }

public void read() {
        root = readTree();
    }

private Node readTree() {
        Node n = new Node();
        
        // get next non-whitespace char
        char ch = in.findInLine("(\\S)").charAt(0);
        if ((ch >= 'a') && (ch <='z')) {
            // leaf node
            n.contents = ch;
            n.left = null;
            n.right = null;
        } else if (ch == '(') {
            // an expression
            n.left = readTree();
            n.contents = in.findInLine("(\\S)").charAt(0);
            n.right = readTree();
            ch = in.findInLine("(\\S)").charAt(0);
            if (ch != ')') {
                System.out.print("EXPECTED ) - } ASSUMED...");
            }
        } else {
            System.out.print("EXPECTED ( - CAN'T PARSE");
            System.exit(1);
        }
        
        return n;
    }
    

public static void main(String[] args) {
        // Read in the expression and build the tree.
        System.out.println("\nType a fully parenthesized expression " +
                           "using a..z,+,-,*,/");
        
        BinaryTree tree = new BinaryTree();
        tree.read();
        System.out.print("\n\n* POSTFIX NOTATION:");
        tree.postorderPrint();
        System.out.println();
    }
}