从保持优先顺序的字符串数组递归构造树数据结构

Question

我目前面临一个问题，我有一个不同字符串的数组，每个字符串代表逻辑和/或比较操作的某些部分，例如：

['Name', '=', 'John', 'and', 'LastName', '!=', 'Doe']

鉴于此，我需要构建一个看起来像这样的树结构：

非常基本的树

这样，每个节点代表一个节点，底部的节点是 LeafNodes，顶部的节点是CompoundNode（如果只有一个节点，那么它本身就是一个 LeafNode）。我面临的问题是，一个简单的复合查询很容易，但是可以有无限的叶节点，以下表达式会在“and”下产生 4 个叶节点：

Name = John and LastName != Doe and City != Amsterdam and BirthYear = 2000

我面临的问题是我不确定如何通过算法解决这个问题。让事情变得更具挑战性的是，如果给出这样的东西：

Price > 10 or (Category = 'Electronics' and Quantity < 100)

，它将创建这样的结构：

稍微复杂一点的树 因此，问题可能会变得无限困难，而这纯粹基于用户输入。优先顺序和构建树本身是我无法弄清楚如何递归执行的事情。我知道我需要遍历字符串，找到叶节点，然后附加到复合节点（如果有的话），但我真的正在努力将这个问题分解为逐渐更复杂的构建块来解决这个问题。

我有以下打字稿类来构造节点：

// Define the types of operators
type LogicalOperator = 'and' | 'or' | 'not';
type ComparisonOperator = 'eq' | 'ne' | 'gt' | 'ge' | 'lt' | 'le' | 'like' | 'ilike' | 'any';
// Interface for internal nodes (logical operators)
interface LogicalNode { 
  operator: LogicalOperator;
  children: FilterNode[]; // Can be any number of children nodes
  // The above would mean 0 as left, 1 as further right etc
}
// Interface for leaf nodes (comparison)
interface ComparisonNode {
  value: string | number; // Value of the leaf node
  field: string; // Field name for comparison nodes
  operator: ComparisonOperator; // Operator for comparison nodes
}
// Union type representing all possible node types
type FilterNode = LogicalNode | ComparisonNode;

我在这里适用于非常简单的复合查询（我删除了相当多的代码来给出要点，是的，目前它是一个相当难看的东西 - 我想以不同的方式重新处理这个问题）：

let i = 1; // First token is always not a comparison or logical operator
while (i < tokens.length) {
  if (COMPARISON_OPERATORS.indexOf(tokens[i]) !== -1) {
     // Will always be left/right operands in this case
     leafNodes.push(this.constructLeafNode(tokens[i - 1], tokens[i], tokens[i + 1]));
     i = i + 2;
  }
  if (LOGICAL_OPERATORS.indexOf(tokens[i]) !== -1) {
     // First leaf node should already be pushed so now we get the 2nd
     leafNodes.push(
       this.constructLeafNode(tokens[i + 1], tokens[i + 2], tokens[i + 3])
     );
     this.constructCompoundNode(leafNodes)
     leafNodes = [] // reset the leaf nodes
     i = i + 4;
  }
}

我的问题是，我希望我能从第二年的数据结构和算法课程中记住更多，但是什么算法/结构最适合这个？当涉及括号或查询中同时存在和/或时，这不起作用

Answer 1

这是一种从左到右优先的实现，以防相继使用两个不同的逻辑运算符。换句话说，逻辑运算符都具有相同的优先级并且是左结合的。

const LOGICAL_OPERATORS = ["and", "or", "not"] as const;
type LogicalOperator = (typeof LOGICAL_OPERATORS)[number];
const isLogicalOperator = (x: any): x is LogicalOperator => LOGICAL_OPERATORS.indexOf(x) != -1;

const COMPARISON_OPERATORS = ["=", "!=", ">", ">=", "<", "<="]
type ComparisonOperator = (typeof COMPARISON_OPERATORS)[number];
const isComparisonOperator = (x: any): x is ComparisonOperator => COMPARISON_OPERATORS.indexOf(x) != -1;

interface LogicalNode { 
    operator: LogicalOperator;
    children: FilterNode[];
}

interface ComparisonNode {
    value: string | number;
    field: string;
    operator: ComparisonOperator;
}

type FilterNode = LogicalNode | ComparisonNode;


function createCompoundNode(operator: string, ...operands: FilterNode[]): LogicalNode {
    if (!isLogicalOperator(operator)) throw Error("Not a logical operator");
    return {
        operator,
        children: operands
    }
}

function createLeafNode(field: string, operator: string, value: string): ComparisonNode {
    if (!isComparisonOperator(operator)) throw Error("Not a comparison operator");
    return {
        operator,
        field,
        value: isNaN(+value) ? value : +value
    }
}

function tokenize(s: string): string[] {
    return s.match(/[-+]?\d+(?:\.\d+)?|\w+|'[^']*'|[<>!=]+|\S/g) ?? [];
}

function parse(tokens: string[]): FilterNode {
    let i = 0;

    const getToken = (): string | undefined => tokens[i++];
    
    const getTerm = (): FilterNode => {
        const token = getToken()!;
        if (token === "(") {
            return getExpression(")");
        }
        if (token === "not") { // Unary operator
            return createCompoundNode("not", getTerm());
        }
        return createLeafNode(token, getToken()!, getToken()!);
    };
    
    const getExpression = (terminal?: string): FilterNode => {
        const term = getTerm()!;
        let operator = getToken();
        if (operator === terminal) {
            return term;
        }
        let expr = createCompoundNode(operator!, term, getTerm()); 
        for (operator = getToken(); operator !== terminal; operator = getToken()) {
            if (operator !== expr.operator) {
                // Apply left associativity
                expr = createCompoundNode(operator!, expr, getTerm());
            } else {
                expr.children.push(getTerm());
            }
        }
        return expr;
    };
    
    return getExpression(undefined);
}

// Demo
const s = "Price > 10 or X != -1.95 or (Category = 'Electronics' and Quantity < 100) and AAA <= 9";
const tokens = tokenize(s);
const tree = parse(tokens);
console.log(JSON.stringify(tree, null, 2));

示例运行的输出是：

{
  "operator": "and",
  "children": [
    {
      "operator": "or",
      "children": [
        {
          "field": "Price",
          "operator": ">",
          "value": "10"
        },
        {
          "field": "X",
          "operator": "!=",
          "value": "-1.95"
        },
        {
          "operator": "and",
          "children": [
            {
              "field": "Category",
              "operator": "=",
              "value": "'Electronics'"
            },
            {
              "field": "Quantity",
              "operator": "<",
              "value": "100"
            }
          ]
        }
      ]
    },
    {
      "field": "AAA",
      "operator": "<=",
      "value": "9"
    }
  ]
}