В настоящее время я столкнулся с проблемой, когда у меня есть массив разных строк, каждая из которых представляет некоторую часть логической операции и/или операции сравнения, например: ['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;
}
}
У меня вопрос, и мне бы хотелось вспомнить больше из моего курса по структурам данных и алгоритмам на втором курсе, но какой алгоритм/структуры лучше всего подойдут для этого? Это не работает, когда используются круглые скобки или когда в запросе есть и то, и другое.
Взгляните на рекурсивный спуск
Правила приоритета всегда будут располагаться слева направо, если есть логические операторы @trincot , но опять же, я могу определить любой набор правил сам, просто это должно иметь смысл, я думаю
В комментарии к коду вы пишете: «... никогда не может быть только одно значение». Как это будет работать с оператором not
?
@trincot, ты прав, это не обязательно так, я удалю комментарий. Код, который у меня есть в настоящее время, я не проверял на «нет» - поскольку с самого начала я пробовал только очень простые запросы.
Сейчас я рассмотрю рекурсивный спуск, спасибо @mochaccino, но, к сожалению, никогда не занимался проектированием компилятора, так что для меня это новый мир.
Вот реализация с приоритетом слева направо в случае, если два разных логических оператора используются один за другим. Другими словами, все логические операторы имеют одинаковый приоритет и левоассоциативны.
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"
}
]
}
Спасибо! Придумал что-то подобное, но скобки пока не работают, так что попробую
Что делать, если у вас есть разные операторы в одной цепочке без круглых скобок, существуют ли какие-либо правила приоритета? Например,
Price > 10 or Category = 'Electronics' and Quantity < 100
... это следует интерпретировать как(Price > 10 or Category = 'Electronics') and Quantity < 100
или какPrice > 10 or (Category = 'Electronics' and Quantity < 100)
?