Source: Expression.js

/*
 *  2016 Maciej Wiecierzewski
 */

/**
 * @constructor
 * @param {Grammar} grammar
 * @returns {Expression}
 */
function Expression(grammar)
{
    this.grammar = grammar;
    this.iterations = 10;
}

/** Generates expression */
Expression.prototype.generateExpression = function()
{
    do
    {
        this.string = this.grammar.symbols[this.grammar.startSymbol].str;
        this.syntaxTree = new Node(this.string, 0);

        this.applyRules(this.iterations);
        
    } while(this.string.length <= this.minExpLength);
    
    this.opOrder = this.figureOpOrder();
}

/**
 * Creates syntax tree basing on given string
 * @param {string} str
 */
Expression.prototype.createFromString = function(str)
{
    console.log(str);
    
    var lastNode = null;
    var pos = 0;
    
    for(var i = 0; i < str.length; i++)
    {
        var char = str.charAt(i);
        
        if(char === "(")
        {
            var node = new Node("", 0);
            if(lastNode !== null)
                lastNode.insertChild(node);
            lastNode = node;
        }
        else if(char === ")")
        {
            lastNode = lastNode.parent;
        }
        else
        {
            var operator = this.findOperator(char);
            
            if(operator.arity === 0)
            {
                var node = new Node(char, pos);
                node.rule = this.findRule(char);
                lastNode.insertChild(node);
            }
            else
            {
                lastNode.rule = this.findRule(char);
                lastNode.pos = pos;
            }
            
            pos++;
        }
    }
    
    this.syntaxTree = lastNode.root;
    this.string = this.syntaxTree.toString({left: "", right: ""})
    
    console.log(this.string);
    console.log(this.syntaxTree.toString());
    
    this.opOrder = this.figureOpOrder(true);
}

/**
 * Returns an 'Operator' object with given symbol
 * @param {type} symbol
 * @returns {Expression.grammar.operators}
 */
Expression.prototype.findOperator = function(symbol)
{
    for(var i = 0; i < this.grammar.operators.length; i++)
    {
        if(this.grammar.operators[i].symbol === symbol)
            return this.grammar.operators[i];
    }
}

/**
 * Returns an 'Rule' object with given operator sybol
 * @param {type} operatorSymbol Character representing operator in the string
 * @returns {Expression.grammar.rules}
 */
Expression.prototype.findRule = function(operatorSymbol)
{
    for(var i = 0; i < this.grammar.rules.length; i++)
    {
        if(this.grammar.rules[i].operator !== null &&
            this.grammar.rules[i].operator === operatorSymbol)
        {
            return this.grammar.rules[i];
        }
    }
}

/** Computes and prints out the probablility of apperance for symbols and operators */
Expression.prototype.expressionProbability = function()
{
    var grammar = this.grammar;
    var symbolsApperanceProb = new Array(grammar.symbols.length);
    var symbolsPickedProb = new Array(grammar.symbols.length);
    var rulesProb = new Array(grammar.rules.length);
    var maxIter = this.iterations;
    var operatorsProb = [];

    symbolsApperanceProb.fill(0);
    symbolsApperanceProb[grammar.startSymbol] = 1;

    while(maxIter --> 0)
    {
        var probSum = symbolsApperanceProb.reduce(
                function(total, currentValue) {
                    return total+currentValue;
                } );

        for(var i = 0; i < symbolsPickedProb.length; i++)
        {
            symbolsPickedProb[i] = symbolsApperanceProb[i] / probSum;
        }

        for(var i = 0; i < symbolsPickedProb.length; i++)
        {
            var symbol = grammar.symbols[i].str;
            var rules = grammar.getRulesN(symbol);

            var probSum = 0;
            for(var j = 0; j < rules.length; j++)
                probSum += grammar.rules[rules[j]].probability;

            for(var j = 0; j < rules.length; j++)
            {
                var n = rules[j];

                rulesProb[n] = symbolsPickedProb[i] * (grammar.rules[n].probability / probSum);

                if(grammar.rules[n].operator !== null)
                {
                    if(operatorsProb[grammar.rules[n].operator])
                        operatorsProb[grammar.rules[n].operator] += rulesProb[n];
                    else
                        operatorsProb[grammar.rules[n].operator] = rulesProb[n];
                }
            }
        }

        var newSymbolsProb = new Array(grammar.symbols.length);
        newSymbolsProb.fill(0);

        for(var i = 0; i < newSymbolsProb.length; i++)
        {
            var symbol = grammar.symbols[i].str;

            for(var j = 0; j < grammar.rules.length; j++)
            {
                if(grammar.rules[j].string.includes(symbol))
                {
                    newSymbolsProb[i] += rulesProb[j];
                }
            }
        }

        var str = "";
        var sum = 0;
        for(var i = 0; i < symbolsApperanceProb.length; i++)
        {
            if(str != "")
                str += ", ";
            str += symbolsApperanceProb[i];
            sum += symbolsApperanceProb[i];
        }
        console.log("symbol apperance: "+str+" sum: "+sum);

        str = "";
        sum = 0;
        for(var i = 0; i < symbolsPickedProb.length; i++)
        {
            if(str != "")
                str += ", ";
            str += symbolsPickedProb[i];
            sum += symbolsPickedProb[i];
        }
        console.log("symbol pict: "+str+" sum: "+sum);

        str = "";
        sum = 0;
        for(var i = 0; i < rulesProb.length; i++)
        {
            if(str != "")
                str += ", ";

            str += rulesProb[i];
            sum += rulesProb[i];
        }
        console.log("rules: "+str+" sum: "+sum);

        str = "";
        sum = 0;
        for(i in operatorsProb)
        {
            if(str != "")
                str += ", ";

            str += "["+i+"]="+operatorsProb[i];
            sum += operatorsProb[i];
        }
        console.log("operators: "+str+" sum: "+sum);

        var total = sum;
        str = "";
        sum = 0;
        for(i in operatorsProb)
        {
            if(str != "")
                str += ", ";

            str += "["+i+"]="+operatorsProb[i]/total*100+"%";
            sum += operatorsProb[i]/total*100;
        }
        console.log("operators%: "+str+" sum: "+sum+"%");

        symbolsApperanceProb = newSymbolsProb;
    }
}

/**
 * Picks randomly a rule from the set
 * @param {Array} rules
 * @returns {String|Expression.prototype.pickRule.rules}
 */
Expression.prototype.pickRule = function(rules)
{
    var probSum = 0;
    for(var i = 0; i < rules.length; i++)
        probSum += rules[i].probability;

    if(probSum == 0)
        return "";

    var segments = [];
    var s = 0;
    for(i in rules)
    {
        s += rules[i].probability/probSum;
        segments.push(s);
    }

    var r = Math.random();
    var i = 0;
    for(i; i < segments.length; i++)
    {
        if(r < segments[i]) break;
    }

    return rules[i];
}

/**
 * Returns symbols in the expression's string
 * @param {string} string Expression's string
 * @param {type} symbols
 * @param {boolean} terminal
 * @returns {Array|Expression.prototype.findSymbols.result}
 */
Expression.prototype.findSymbols = function(string, symbols, terminal)
{
    var result = [];
    for(var i in symbols)
    {
        if(symbols[i].terminal == terminal)
        {
            for(var j = 0; j < string.length; j++)
            {
                if(string[j] == symbols[i].str)
                    result.push(j);
            }
        }
    }

    return result;
}

/**
 * Returns nonterminal symbols in the expression's string
 * @param {type} string
 * @param {type} symbols
 * @returns {Array|Expression.prototype.findSymbols.result}
 */
Expression.prototype.nonTerminalSymbols = function(string, symbols)
{
    return this.findSymbols(string, symbols, false);
}

/**
 * Returns terminal symbols in the expression's string
 * @param {type} string
 * @param {type} symbols
 * @returns {Array|Expression.prototype.findSymbols.result}
 */
Expression.prototype.terminalSymbols = function(string, symbols)
{
    return this.findSymbols(string, symbols, true);
}

/**
 * Replaces symbol in string according to given rule and adds new node in the syntax tree
 * @param {number} symbolPos
 * @param {Rule} rule
 */
Expression.prototype.applyRule = function(symbolPos, rule)
{
    var node = this.syntaxTree.findNode(symbolPos);
    if(node.children.length > 0) console.log("@err");
    
    node.setRule(rule);     // adds new node
    
    var replacement = rule.string;
    this.string = this.string.substr(0, symbolPos)+replacement+this.string.substr(symbolPos+1, this.string.length-symbolPos-1);
}

/**
 * Builds expression by picking a random symbol and chosing a matching rule
 * @param {numbers} iter How many times a symbol will be substited
 */
Expression.prototype.applyRules = function(iter)
{   
    var grammar = this.grammar;
    var rules = grammar.rules;
    var endRules = grammar.endRules;
    var symbols = grammar.symbols;

    var symbolsPos = this.nonTerminalSymbols(this.string, symbols);

    while(symbolsPos.length > 0 && iter --> 0)
    {
        var i = Math.round(Math.random()*(symbolsPos.length-1));
        var symbolPos = symbolsPos[i];
        var symbol = this.string.substr(symbolPos, 1);

        var _rules = grammar.getRules(symbol);
        var rule = this.pickRule(_rules);
        
        this.applyRule(symbolPos, rule);

        symbolsPos = this.nonTerminalSymbols(this.string, symbols);
    }

    this.ridNonterminals();
    this.finish();
}

/** Replaces all nonterminal symbols with matching rules */
Expression.prototype.ridNonterminals = function()
{
    var grammar = this.grammar;
    var rules = grammar.rules;
    var endRules = grammar.endRules;
    
    for(var i = 0; i < endRules.length; i++)
    {
        var endRule = endRules[i];
        var symbol = rules[endRule].symbol;
        var replacement = rules[endRule].string;
        var regExp = new RegExp(symbol, 'g');
        this.string = this.string.replace(regExp, replacement);
    }
}

/** Replaces terminal symbols with operators so there is no symbols left */
Expression.prototype.finish = function()
{
    var grammar = this.grammar;
    var rules = grammar.rules;
    var symbols = grammar.symbols;
    
    var symbolsPos = this.terminalSymbols(this.string, symbols);

    while(symbolsPos.length > 0)
    {
        var symbolPos = symbolsPos[0];
        var symbol = this.string.substr(symbolPos, 1);

        var _rules = grammar.getRules(symbol);
        var rule = this.pickRule(_rules);

        this.applyRule(symbolPos, rule);

        symbolsPos = this.terminalSymbols(this.string, symbols);
    }
}

/**
 * Figures out the order of operators
 * @param {type} noPosShift
 * @returns {Array|Expression.prototype.figureOpOrder.nArr}
 * @todo rewrite it
 */
Expression.prototype.figureOpOrder = function(noPosShift)
{
    function Order(pos, no)
    {
        this.pos = pos;
        this.no = no;
    }
    
    this.getOrder = function(pos)
    {
        return this.opOrder[pos];
    }
    
    function compare(a, b)
    {
        var aInt = parseInt(a.pos);
        var bInt = parseInt(b.pos);

        if(aInt > bInt) return 1;
        else if(aInt == bInt) return 0;
        else if(aInt < bInt) return -1;
    }

    function Entry(pos, order)
    {
        this.pos = pos;
        this.order = order;
    }

    function getLength(node)
    {
        if(node.rule == null)
            return 0;

        var z = node.rule.string.length - 1;

        for(var i = 0; i < node.children.length; i++)
        {
            z += getLength(node.children[i]);
        }

        return z;
    }

    function getSymbolPos(node)
    {
        var pos = 0;
        var childNo = 0;
        var z = 0;

        for(var i = 0; i < node.rule.string.length; i++)
        {
            if(node.rule.string.charAt(i) === node.rule.operator)
            {
                pos = (node.pos + z + i);
            }
            else
            {
                z += getLength(node.children[childNo]);
                childNo++;
            }
        }

        return pos;
    }

    function getEntries(node)
    {
        if(noPosShift)
            arr.push(new Entry(node.pos, node.order));
        else
            arr.push(new Entry(getSymbolPos(node), node.order));

        for(var i = 0; i < node.children.length; i++)
        {
            getEntries(node.children[i]);
        }
    }

    this.syntaxTree.figureOrder();

    var arr = [];
    getEntries(this.syntaxTree);
    arr.sort(compare);

    var nArr = [];
    
    var str = "";
    for(var i = 0; i < arr.length; i++)
    {
        if(str != "")
            str += "  ";
        
        var order = arr.length - arr[i].order + 1;
        //str += "["+arr[i].pos+"] = "+order;
        str += order;
        
        nArr.push(order);
    }
    console.log(str);

    return nArr;
}