JS boolean polish notation converter

scary_poles.js

"use strict";
const AND = 'AND',
OR = 'OR';
function parsePoleBools(arr){
    /*
    takes:
    an array of:
        bools and/or functions that evaluate to bools
        tokens representing boolean comparison
        (all in reverse polish notation order)
    returns:
        boolean representing the final evaluation
    logs:
        educational output demonstrating how polish notation functions
    notes:
        cost factor of this is -sort of- linear, but we're executing N unknown functions.
        so, all bets are off, really. 
    */
    while (arr.length > 1) {
        var andI = arr.indexOf(AND),
        orI = arr.indexOf(OR),
        I,
        useAnd;
        //first we find the left most and/or token, and log if it was AND or OR
        if (andI != -1 && andI < orI || orI == -1){
            I = andI;
            useAnd = true;
        }else{
            I = orI;
            useAnd = false; //implict OR token
        };
        if (andI == -1 && orI == -1){
        //We're out of AND/OR tokens and our list has more than one bool, thus, fail
            throw "Operator/Operand Mismatch" 
        }
        //now we note where we found our token,
        //and save the left two bools for comparison
        var item = arr[I],
        lft = arr[I - 2],
        rgt = arr[I - 1];
        //if our bools are functions, eval them so we can compare the results
        typeof lft == 'function' ? lft = lft() : lft = lft;
        typeof rgt == 'function' ? rgt = rgt() : rgt = rgt;
        //log the state of our list and what we're doing so people can see it work
        console.log(item,arr);
        //decide which eval statement we're using,
        //and mutate the array with the result of our eval statement
        if (useAnd){
            arr.splice(I-2,3,(lft && rgt)) 
        }else{
            arr.splice(I-2,3,(lft || rgt))
        }
    }
    //the last item standing is the result of all our evals
    return arr[0]
}
function poleMaker(list){
    /*
    takes:
    an Array of:
        Parentheses (string)
        functions that eval to bool
        tokens representing boolean operations
    returns:
        a sorted array of the input items sorted into polish notation
    notes:
        common parlance for this algorithm is the 'shunting yard algorithm'
        this implementation takes some shortcuts because we assume the only operations are
        boolean evaluations, so we don't need to care about # of args or operator precedence.
        cost factor is linear.

    */
    //queue here represents our array of tokens and functions. 
    //stack represents where we store crap while we figure out about parens.
    var stack = [],
    queue = [];
    for (var x of list){
        //functions just go straight on the list.
        if (typeof x == 'function'){
            queue.push(x)
        }
        //tokens go on the stack
        if ([AND,OR].indexOf(x) != -1) {
            stack.push(x)
            //if our stack isn't being a packrat after encountering a parens
            //we only stow a max of one operator at a time
            if (stack.indexOf('(') == -1 && stack.length > 1){
                queue.push(stack.shift())
            }
        }
        //LEFT parens go on the stack
        if (x == '('){
            stack.push(x)
        }
        //RIGHT Parens make magic go time happen fun fun
        if (x == ')'){
            let f = stack.lastIndexOf('('), // set a marker at last paren
            g = stack.length;
            if (f == -1){
                //This would be bad.
                throw "Paren Mismatch"
            }

            stack.splice(f,1) //drop lParens like it's hot
            //grab everything after where that left paren was
            //spin it around, slap it onto our queue (as if we'd individually 
            //shift()ed each item out of the stack onto the queue)
            queue = queue.concat(stack.splice(f,g).reverse())

        }
        //at the end of every loop, be a good boy and show us every variable forever.
        console.log('Q : ',queue);
        console.log('S : ',stack);
    };
    console.log('final q: ', queue)
    if (stack.length == 1){
        queue.push(stack[0])
        return queue
    }else{

        //if our stack still has stuff in it, we did something wrong somewhere
        throw "Polish stack error"
    }
}
// possibly the worlds ugliest test case:
function yes(){
return true
}
function no(){
return false
}
var testIn = [yes,'AND','(',no,'OR','(',yes,'OR',no,')','AND','(',yes,'AND','(',no,'OR',yes,')','OR','(',yes,'AND','(',no,'OR','(',yes,'AND',yes,')','OR','(',yes,'AND','(',no,'OR','(',no,'AND','(',no,'OR',no,')',')',')',')',')',')',')',')','OR',yes];
var poleypoles = poleMaker(testIn);
parsePoleBools(poleypoles);

This is an example of how to implement a conditional parser for boolean evaluation of input conditions using polish notation.

Why?

Because, for example, you could be building a query language, or an API for interrogating objects that needs to be extensible enough to handle advanced filters.

You could then use this technique to take a list of 'does match' and 'does match' or 'doesn't match' type functions, and string them together endlessly to make arbitrarly complex filters.