二进制表达式树的缀

Sumeet 发表于 Dev

苏梅特

我有像这样的中缀表达式：

((source = id)AND (target= id) AND ( NOT( color != blue) OR ( age<= 23 )))

如何转换成二叉树，应该像下面的树形图。我刚刚开始用javascript编写代码，但不知道如何编写插入操作，尤其是像NOT这样的一元运算符。如何解决这个问题呢。

var Node = function(data,left,right){
    this.data = data;
    this.left = left;
    this.right = right;
};


var BinaryTree = function(){
    this.head = new Node(null,null,null);
};

BinaryTree.prototype.insert = function(data){
    if(this.head.data == null){
        this.head = new Node(data,null,null);
    } else{
        var current = this.head;
        insert(current,data);
    }
};

var insert = function(current,data){
    // How to insert ?
};

汤玛士

正如昨晚所说的，这里是我要去的要点：

图节点：

//abstract base-class
class GraphNode {
    constructor(){
        Object.defineProperty(this, "parent", {
            writable: true,
            //enumerable: false,    //so it doesn't show up in JSON
            value: null
        })
    }
    compute(ctx){ throw new Error("not implemented") }
    toString(){ throw new Error("not implemented") }
}

//leaf-nodes
class ValueNode extends GraphNode{
    constructor(value){ 
        super();
        this.value = value; 
    }
    compute(){ return this.value; }
    toString(){ return JSON.stringify(this.value); }
}

class PropertyNode extends GraphNode{
    constructor(property){
        super();
        this.property = property;
    }
    compute(ctx){ return ctx[this.property]; }
    toString(){ return String(this.property); }
}

//tree-nodes
class UnaryNode extends GraphNode{
    constructor(op, node){
        if(!(node instanceof GraphNode)){
            throw new Error("invalid node passed")
        }
        super();
        this.op = op;
        this.node = node;
        node.parent = this;
    }
    compute(ctx){
        var v = this.node.compute(ctx);
        switch(this.op){
            case "NOT": return !v;
        }
        throw new Error("operator not implemented '"+this.op+"'");
    }
    toString(){
        return  "( " + this.op + " " + this.node.toString() + " )";
    }   
}
UnaryNode.operators = ["NOT"];


class BinaryNode extends GraphNode{
    constructor(op, l, r){
        if(!(l instanceof GraphNode && r instanceof GraphNode)){
            throw new Error("invalid node passed")
        }
        super();
        this.op = op;
        this.left = l;
        this.right = r;
        l.parent = this;
        r.parent = this;
    }
    compute(ctx){
        var l = this.left.compute(ctx);
        var r = this.right.compute(ctx);
        switch(this.op){
            //logic operators
            case "AND": return l && r;
            case "OR": return l || r;

            //comparison-operators
            case "=": return l === r;
            case "<=": return l <= r;
            case ">=": return l >= r;
            case "!=": return l != r;
            case ">": return l > r;
            case "<": return l < r;

            //computational operators
            case "+": return l + r;
            case "-": return l - r;
            case "*": return l * r;
            case "/": return l / r;
        }
        throw new Error("operator not implemented '"+this.op+"'");
    }

    toString(){
        return "( " + this.left.toString() + " " + this.op + " " + this.right.toString() + " )";
    }
}
//also defines precendence
BinaryNode.operators = [
    "*","/","+","-",
    ">","<","<=",">=","!=","=",
    "AND","OR",
]

//dot is kind of special:
class DotNode extends BinaryNode{
    constructor(l, r){
        /*
        if(!(l instanceof PropertyNode || l instanceof DotNode)){
            throw new Error("invalid left node")
        }
        */
        if(!(r instanceof PropertyNode)){
            throw new Error("invalid right node")
        }
        super(".", l, r);
    }

    compute(ctx){
        //especially because of this composition:
        //fetch the right property in the context of the left result
        return this.right.compute( this.left.compute(ctx) );
    }
    toString(){
        return this.left.toString() + "." + this.right.toString();
    }
}

解析器：

function escapeForRegex(str){
    return String(str).replace(/[.*+?^=!:${}()|[\]\/\\]/g, '\\$&');
}

//dynamically build my parsing regex:
var tokenParser = new RegExp([
        //numbers
        /\d+(?:\.\d*)?|\.\d+/.source,

        //string-literal
        //  /["](?:\\[\s\S]|[^"])+["]|['](?:\\[\s\S]|[^'])+[']/.source,

        //booleans
        //"true|false",

        //operators
        [".", "(", ")"].concat(UnaryNode.operators, BinaryNode.operators)
            .sort((a,b) => b.length-a.length) //so that ">=" is added before "=" and ">", for example
            .map(escapeForRegex)
            .join("|"),

        //properties
        //has to be after the operators
        /[a-zA-Z$_][a-zA-Z0-9$_]*/.source,

        //remaining (non-whitespace-)chars, just in case
        //has to be at the end
        /\S/.source
    ].map(s => "("+ s +")").join("|"), "g");

function parse(str){
    var tokens = [];
    //abusing str.replace() as a RegExp.forEach
    str.replace(tokenParser, function(token, number, op, property){
        if(number){
            token = new ValueNode(+number);
        //}else if(string){
        //  token = new ValueNode(JSON.parse(string));      
        //}else if(bool){
        //  token = new ValueNode(bool === "true");
        }else if(property){
            token = new PropertyNode(property);
        }else if(!op){
            throw new Error("unexpected token '"+token+"'");
        }
        tokens.push(token);
    });

    for(var i; (i=tokens.indexOf(".")) > -1; ){
        tokens.splice(i-1, 3, new DotNode(tokens[i-1], tokens[i+1]))
    }

    for(var i,j; (i=tokens.lastIndexOf("(")) > -1 && (j=tokens.indexOf(")", i)) > -1;){
        tokens.splice(i, j+1-i, process(tokens.slice(i+1, j)));
    }
    if(~tokens.indexOf("(") || ~tokens.indexOf(")")){
        throw new Error("mismatching brackets");
    }

    return process(tokens);
}

function process(tokens){
    UnaryNode.operators.forEach(token => {
        for(var i=-i; (i=tokens.indexOf(token, i+1)) > -1;){
            tokens.splice(i, 2, new UnaryNode(token, tokens[i+1]));
        }
    })

    BinaryNode.operators.forEach(token => {
        for(var i=1; (i=tokens.indexOf(token, i-1)) > -1;){
            tokens.splice(i-1, 3, new BinaryNode(token, tokens[i-1], tokens[i+1]));
        }
    });

    if(tokens.length !== 1){
        console.log("error: ", tokens.slice());
        throw new Error("something went wrong");
    }
    return tokens[0];
}

它的用法是：

var tree = parse("((a.source = id)AND (target= id) AND ( NOT( color != blue) OR ( age<= 23 )))")
//var tree = parse("1=1=age+10>30"); //to test operator precedence

var data = {
    id: 12345,

    a: { source: 12345 },
    target: 12345,

    color: "#FF0",
    blue: "#00F",

    age: 20
}

console.log(tree.compute(data));
console.log(tree.toString());
console.log(JSON.stringify(tree, null, 2));