Source: ExpressionTree.js

const BinaryNode = require('./BinaryNode');

/** A specific kind of a binary tree used to represent expressions */
class ExpressionTree {
    /**
     * Construct an expression tree object representing an expression
     * 
     * @param {string} expressionString The expression used to build this tree
     */
    constructor(expressionString) {
        /** The expression used to build this tree */
        this.expressionString = expressionString;
        /** The root node of this tree */
        this.root = this.buildTree(this.expressionString);
    }
    
    /**
     * Build an expression tree representing an expression; ERASES CURRENT TREE DATA ON THIS OBJECT
     * 
     * @param {string} expressionString The expression used to build this tree
     */
    buildTree(expressionString) {
        if (this.expressionString !== expressionString) this.expressionString = expressionString;
        const expression = [...expressionString];
        let node = new BinaryNode(null, null, null);
        node.data = this.findLowestPrecedence(expression).lowestPrecedenceOperator;
        if (!node.data) node.data = expressionString;
        else node = this.buildNodePointers(node, expression);
        return node;
    }

    /**
     * Returns information regarding the operator of lowest precedence
     * 
     * @param {string[]} expression The expression whose operators are being analyzed
     */
    findLowestPrecedence(expression) {
        let globalParenthesisDepth = 0;
        let precedenceValues = { "lowestPrecedenceIndex": 0, "lowestPrecedenceOperator": null, "parenthesisDepth": 0 };
        for (let i = 0; i < expression.length; ++i) {
            if (expression[i] === '(') ++globalParenthesisDepth; else if (expression[i] === ')') --globalParenthesisDepth;
                if (!precedenceValues.lowestPrecedenceOperator) {
                    if (expression[i] === '+' || expression[i] === '-' || expression[i] === '*' || expression[i] === '/' || expression[i] === '^') {
                        precedenceValues.lowestPrecedenceIndex = i;
                        precedenceValues.lowestPrecedenceOperator = expression[i];
                        precedenceValues.parenthesisDepth = globalParenthesisDepth;
                    }
                }
                switch (expression[i]) {
                    case '+':
                    case '-':
                        if (globalParenthesisDepth <= precedenceValues.parenthesisDepth) {
                            precedenceValues.lowestPrecedenceIndex = i;
                            precedenceValues.lowestPrecedenceOperator = expression[i];
                            precedenceValues.parenthesisDepth = globalParenthesisDepth;
                        }
                        break;
                    case '*':
                    case '/':
                    case '%':
                        if (globalParenthesisDepth < precedenceValues.parenthesisDepth || (globalParenthesisDepth == precedenceValues.parenthesisDepth && precedenceValues.lowestPrecedenceOperator !== '+' && precedenceValues.lowestPrecedenceOperator !== '-')) {
                            precedenceValues.lowestPrecedenceIndex = i;
                            precedenceValues.lowestPrecedenceOperator = expression[i];
                            precedenceValues.parenthesisDepth = globalParenthesisDepth;
                        }
                        break;
                    case '^':
                        if (globalParenthesisDepth < precedenceValues.parenthesisDepth || (globalParenthesisDepth == precedenceValues.parenthesisDepth && precedenceValues.lowestPrecedenceOperator !== '+' && precedenceValues.lowestPrecedenceOperator !== '-' && precedenceValues.lowestPrecedenceOperator !== '*' && precedenceValues.lowestPrecedenceOperator !== '/')) {
                            precedenceValues.lowestPrecedenceIndex = i;
                            precedenceValues.lowestPrecedenceOperator = expression[i];
                            precedenceValues.parenthesisDepth = globalParenthesisDepth;
                        }
                        break;
                    default:
                        break;
                }
        }
        return precedenceValues;
    }

    /**
     * Attemps to reconfigure a binary node's null pointers so they will each point to another node
     * 
     * @param {BinaryNode} node The node whose pointers are being built
     * @param {string[]} expression The mathematical expression that will be used to build this node
     */
    buildNodePointers(node, expression) {
        if (expression[0] === '(' && expression[expression.length - 1] === ')') {
            (() => {
                for (let parenthesisDepth = 1, i = 1; i < expression.length - 1; ++i) {
                    if (expression[i] === '(') ++parenthesisDepth; else if(expression[i] === ')') --parenthesisDepth;
                    if (parenthesisDepth < 1) return;
                }
                expression.splice(expression.length - 1, expression.length);
                expression.splice(0, 1);
            })();
        }
        const splitIndex = this.findLowestPrecedence(expression).lowestPrecedenceIndex;
        return new BinaryNode(
            this.buildNode(expression.slice(0, splitIndex)),
            this.buildNode(expression.slice(splitIndex + 1, expression.length)),
            node.data
        );
    }

    /**
     * Builds a single node with null pointers. If this is the last node in the sequence, it will have a numeric/variable value, otherwise it will be an operator
     * 
     * @param {string} operator The value to be placed in this node if operator is defined and not null
     * @param {string[]} expression The mathematical expression that will be used to build the pointers to the next nodes
     * @returns {BinaryNode} A binary node
     */
    buildNode(expression) {
        const lowestPrecedence = this.findLowestPrecedence(expression);
        if (!lowestPrecedence.lowestPrecedenceOperator) return new BinaryNode(null, null, expression.join(''));
        return this.buildNodePointers(
            new BinaryNode(null, null, lowestPrecedence.lowestPrecedenceOperator),
            expression
            );
    }
    
    /**
     * Check if an object is equal to this object
     * 
     * @param {*} obj The object that will be compared with this object
     */
    isEqual(obj) {
        return this.solveTree() === obj.solveTree();
    }
}

module.exports = ExpressionTree;