package trees;

class ExprTree {
    class Node {
        private Object item;
        private Node left;
        private Node right;

        public Node(Object item) {
            this(item, null, null);
        }

        public Node(Object item, Node left, Node right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }

        private void visit() {
            System.out.print(item + " ");
        }

        public void preorder() {
            visit();
            if (left != null)
                left.preorder();
            if (right != null)
                right.preorder();
        }

        public void postorder() {
            if (left != null)
                left.postorder();
            if (right != null)
                right.postorder();
            visit();
        }

        public void inorder() {
            if (left != null)
                left.inorder();
            visit();
            if (right != null)
                right.inorder();
        }

        public int evaluate() {
            String item = (String) this.item;
            int value = 0;
            if (Character.isDigit(item.charAt(0)))
                value = Integer.parseInt(item);
            else {
                int lval = left.evaluate();
                int rval = right.evaluate();
                if (item.equals("+"))
                    value = lval + rval;
                else if (item.equals("-"))
                    value = lval - rval;
                else if (item.equals("*"))
                    value = lval * rval;
                else if (item.equals("/"))
                    value = lval / rval;
            }
            return value;
        }

        private final boolean[] regs = { true, true, true, true };

        private int allocReg() {
            int i;
            for (i = 0; i < regs.length; i++)
                if (regs[i] == true)
                    break;
            regs[i] = false;
            return i;
        }

        private void freeReg(int reg) {
            regs[reg] = true;
        }

        public int code() {
            String item = (String) this.item;
            int register;
            if (Character.isDigit(item.charAt(0))) {
                int value = Integer.parseInt(item);
                register = allocReg();
                System.out.println("ld" + " " + "r" + register + " " + value);
            } else {
                String opcode = null;
                if (item.equals("+"))
                    opcode = "add";
                else if (item.equals("-"))
                    opcode = "sub";
                else if (item.equals("*"))
                    opcode = "mul";
                else if (item.equals("/"))
                    opcode = "div";
                int lreg = left.code();
                int rreg = right.code();
                register = allocReg();
                System.out.println(opcode + " " + "r" + register + " " + "r"
                        + lreg + " " + "r" + rreg);
                freeReg(lreg);
                freeReg(rreg);
            }
            return register;
        }
    }

    public Node makeTree() {
        return new Node("*", new Node("+", new Node("*", new Node("2"),
                new Node("4")), new Node("/", new Node("8"), new Node("4"))),
                new Node("-", new Node("2"), new Node("4")));
    }

    public static void main(String[] args) {
        ExprTree e = new ExprTree();
        Node tree = e.makeTree();
        System.out.println("PREorder");
        tree.preorder();
        System.out.println();
        System.out.println("POSTorder");
        tree.postorder();
        System.out.println();
        System.out.println("INorder");
        tree.inorder();
        System.out.println();
        System.out.println("EVAL");
        System.out.println(tree.evaluate());
        System.out.println("CODE");
        System.out.println(tree.code());
    }
}