Разбор и построение S-выражений с использованием наборов и дерева двоичного поиска

Это псевдо домашняя работа (это дополнительный кредит). У меня есть BST, который является индексом слов, указывающих на строки (хранящиеся где-то еще), содержащие слова. Мне нужно реализовать способ поиска с использованием s-выражений, чтобы я мог комбинировать и (&) и/или (|).

В командной строке пользователь может ввести что-то вроде:

QUERY ((((fire)&(forest))|((ocean)&(boat)))&(water))

По существу, это должно возвращать все строки, содержащие слова: огонь, лес и вода, а также все линии, содержащие океан, лодку и воду.

Мне нужна помощь в логике для синтаксического анализа и вставки узлов в дерево, чтобы правильно представлять выражение больше, чем фактический код. Единственное, что я разработал, что имеет смысл для меня, это вернуть набор строк для каждого слова в выражении. Тогда в зависимости от того, была ли это операция "или" или "и", я бы выполнил операцию объединения или типа пересечения на этих наборах, чтобы создать новый набор и передать это по дереву.

Я как бы потерял, как разбирать строку, содержащую выражение. После некоторого раздумья кажется, что "дальше" из одного из подвыражений, чем выше он должен быть в моем дереве s-expression? Я думаю, что если бы я мог просто нажать в правильном направлении, чтобы разобрать и вставить выражения в дерево, я должен быть в порядке.

Мое дерево образцов, которое я придумал для запроса выше, выглядит примерно так:

                                            &
                                         /     \
                                       |       water
                                   /      \
                                 &          &
                               /   \        /   \
                            fire  forest  ocean boat

Это имеет смысл, поскольку огонь возвратит набор строк, которые содержат огонь и лес, возвратит набор линий, в которых все будут содержать лес. Затем на "&" уровень я взял бы эти два набора и создал бы другой набор, содержащий только строки, которые были в обоих наборах, тем самым давая мне набор, который имеет только строки, которые содержат как огонь, так и лес.

Еще один камень преткновения - как представить все в дереве после преодоления барьера синтаксического разбора. У меня есть класс ExpTreeNode, который будет служить узлом для моего ExpTree (BST), а затем у меня есть 2 подкласса, оператор и операнд, но я не уверен, что это хороший подход.

Ответы

Ответ 1

Dijkstra сделал это для вас уже: -)

Попробуйте алгоритм шунтирования: http://en.wikipedia.org/wiki/Shunting-yard_algorithm

Вы можете создать RPN (обратная полировка) с использованием алгоритма маневрового двора, и как только он будет создан, вы можете сделать проход через него, чтобы создать двоичное дерево.

Обычно RPN используется для оценки, но вы можете фактически создать дерево.

Например, вместо оценки вы создаете узлы дерева и вставляете их в стек.

Итак, если вы видите оператор node1, node2,. Вы создаете новый node

   Operator
   /     \
  node1   node2

и верните его в стек.

Более подробный пример:

Скажем, выражение (apples AND oranges) OR kiwis

Для RPN это kiwis oranges apples AND OR

Теперь выполняйте это при сохранении стека.

Сделайте node из киви, нажав на стек. node из апельсинов нажмите на стек. То же самое с яблоками.

Итак, стек

Node:Apples
Node:Oranges
Node:Kiwis

Теперь вы видите И в RPN.

Вы поместите верхние два из стека и создайте новый node с родительским элементом AND.

Node: И, [ Node: Яблоки, Node: Апельсины]

в основном дерево

       AND
     /    \
  Apples  Oranges

Теперь переместите этот node в стек.

Итак, стек

Node:AND, [Node:Apples, Node:Oranges]
Node:Kiwis

Теперь вы видите OR в RPN и создаете node с OR как родительский и Node: ANd и node Kiwis, поскольку дети получают дерево

           OR 
         /   \
       AND   Kiwis
     /    \
  Apples  Oranges

Возможно, вы даже сможете модифицировать алгоритм шунтирования, чтобы создать дерево, но работать с RPN проще.

В качестве альтернативы вы можете попробовать использовать методы анализа рекурсивного спуска. То, что вы просите, очень распространено, и вы сможете найти грамматики и код даже, если вы ищете в Интернете.

Кстати, вы просто имеете в виду двоичное дерево? BST (Дерево двоичного поиска) имеет дополнительное ограничение...