缀以二进制表达式树

Question

我缀表达式，如：

((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 ? 
}; 

Answer 1

至于谈到昨晚，点这里我得：

图形节点：

//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));