Рекурсивное построение древовидной структуры данных из массива строк, сохраняющих порядок приоритета

В настоящее время я столкнулся с проблемой, когда у меня есть массив разных строк, каждая из которых представляет некоторую часть логической операции и/или операции сравнения, например: ['Name', '=', 'John', 'and', 'LastName', '!=', 'Doe']

Учитывая это, мне нужно будет построить древовидную структуру, которая будет выглядеть примерно так:

Очень простое дерево

При этом каждый представляет собой узел, причем нижние из них являются LeafNodes, а верхние — CompoundNode (который, если есть только один узел, сам является LeafNode). Проблема, с которой я столкнулся, заключается в том, что простой составной запрос достаточно прост, но может быть бесконечное количество листовых узлов, а следующее выражение приводит к 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;
  }
}

У меня вопрос, и мне бы хотелось вспомнить больше из моего курса по структурам данных и алгоритмам на втором курсе, но какой алгоритм/структуры лучше всего подойдут для этого? Это не работает, когда используются круглые скобки или когда в запросе есть и то, и другое.

Что делать, если у вас есть разные операторы в одной цепочке без круглых скобок, существуют ли какие-либо правила приоритета? Например, Price > 10 or Category = 'Electronics' and Quantity < 100... это следует интерпретировать как (Price > 10 or Category = 'Electronics') and Quantity < 100 или как Price > 10 or (Category = 'Electronics' and Quantity < 100)?

trincot 04.04.2024 16:33

Взгляните на рекурсивный спуск

mochaccino 04.04.2024 16:49

Правила приоритета всегда будут располагаться слева направо, если есть логические операторы @trincot , но опять же, я могу определить любой набор правил сам, просто это должно иметь смысл, я думаю

Shaun Yates 04.04.2024 16:51

В комментарии к коду вы пишете: «... никогда не может быть только одно значение». Как это будет работать с оператором not?

trincot 04.04.2024 17:03

@trincot, ты прав, это не обязательно так, я удалю комментарий. Код, который у меня есть в настоящее время, я не проверял на «нет» - поскольку с самого начала я пробовал только очень простые запросы.

Shaun Yates 04.04.2024 17:09

Сейчас я рассмотрю рекурсивный спуск, спасибо @mochaccino, но, к сожалению, никогда не занимался проектированием компилятора, так что для меня это новый мир.

Shaun Yates 04.04.2024 17:10
Зод: сила проверки и преобразования данных
Зод: сила проверки и преобразования данных
Сегодня я хочу познакомить вас с библиотекой Zod и раскрыть некоторые ее особенности, например, возможности валидации и трансформации данных, а также...
Как заставить Remix работать с Mantine и Cloudflare Pages/Workers
Как заставить Remix работать с Mantine и Cloudflare Pages/Workers
Мне нравится библиотека Mantine Component , но заставить ее работать без проблем с Remix бывает непросто.
Угловой продивер
Угловой продивер
Оригинал этой статьи на турецком языке. ChatGPT используется только для перевода на английский язык.
TypeScript против JavaScript
TypeScript против JavaScript
TypeScript vs JavaScript - в чем различия и какой из них выбрать?
Синхронизация localStorage в масштабах всего приложения с помощью пользовательского реактивного хука useLocalStorage
Синхронизация localStorage в масштабах всего приложения с помощью пользовательского реактивного хука useLocalStorage
Не все нужно хранить на стороне сервера. Иногда все, что вам нужно, это постоянное хранилище на стороне клиента для хранения уникальных для клиента...
Что такое ленивая загрузка в Angular и как ее применять
Что такое ленивая загрузка в Angular и как ее применять
Ленивая загрузка - это техника, используемая в Angular для повышения производительности приложения путем загрузки модулей только тогда, когда они...
0
6
111
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 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.info(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"
    }
  ]
}

Спасибо! Придумал что-то подобное, но скобки пока не работают, так что попробую

Shaun Yates 09.04.2024 08:31

Другие вопросы по теме

Похожие вопросы