package week6;


import week4.ArrayUnorderedList;
import week4.UnorderedListADT;

public class ExpressionTree extends LinkedBinaryTree<ExpressionTreeOp>
{
    // 创建一个空的表达式树
    public ExpressionTree()
    {
        super();
    }

    // 从两个指定的表达式构造表达式树
    public ExpressionTree(ExpressionTreeOp element,
                          ExpressionTree leftSubtree, ExpressionTree rightSubtree)
    {
        root = new BinaryTreeNode<ExpressionTreeOp>(element, leftSubtree, rightSubtree);
    }

    // 通过调用递归计算表达式树evaluateNode方法。
    public int evaluateTree()
    {
        return evaluateNode(root);
    }

    // 递归地计算树的每个节点。
    public int evaluateNode(BinaryTreeNode root)
    {
        int result, operand1, operand2;
        ExpressionTreeOp temp;

        if (root==null)
            result = 0;
        else
        {
            temp = (ExpressionTreeOp)root.getElement();

            if (temp.isOperator())
            {
                operand1 = evaluateNode(root.getLeft());
                operand2 = evaluateNode(root.getRight());
                result = computeTerm(temp.getOperator(), operand1, operand2);
            }
            else
                result = temp.getValue();
        }

        return result;
    }

    // 计算一个由运算符和两个操作数组成的术语。
    private static int computeTerm(char operator, int operand1, int operand2)
    {
        int result=0;

        if (operator == '+')
            result = operand1 + operand2;

        else if (operator == '-')
            result = operand1 - operand2;
        else if (operator == '*')
            result = operand1 * operand2;
        else
            result = operand1 / operand2;

        return result;
    }

    // 通过执行生成树的结构化字符串版本层次遍历。
    public String printTree()
    {
        UnorderedListADT<BinaryTreeNode<ExpressionTreeOp>> nodes =
                new ArrayUnorderedList<BinaryTreeNode<ExpressionTreeOp>>();
        UnorderedListADT<Integer> levelList =
                new ArrayUnorderedList<Integer>();
        BinaryTreeNode<ExpressionTreeOp> current;
        String result = "";
        int printDepth = this.getHeight();
        int possibleNodes = (int)Math.pow(2, printDepth + 1); // 最多的结点数 + 1
        int countNodes = 0;

        nodes.addToRear(root);
        Integer currentLevel = 0;
        Integer previousLevel = -1;
        levelList.addToRear(currentLevel);

        while (countNodes < possibleNodes)
        {
            countNodes = countNodes + 1;
            current = nodes.removeFirst();
            currentLevel = levelList.removeFirst();
            if (currentLevel > previousLevel)
            {
                result = result + "\n\n";
                previousLevel = currentLevel;
                for (int j = 0; j < ((Math.pow(2, (printDepth - currentLevel))) - 1); j++)
                    result = result + " ";
            }
            else
            {
                for (int i = 0; i < ((Math.pow(2, (printDepth - currentLevel + 1)) - 1)) ; i++)
                {
                    result = result + " ";
                }
            }
            if (current != null)
            {
                result = result + (current.getElement()).toString();
                nodes.addToRear(current.getLeft());
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(current.getRight());
                levelList.addToRear(currentLevel + 1);
            }
            else {
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                result = result + " ";
            }

        }

        return result;
    }
}