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

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

0 голосов
/ 13 апреля 2011

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

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

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

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

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

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

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

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

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

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

1 Ответ

4 голосов
/ 13 апреля 2011

Дейкстра уже сделал это для вас: -)

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

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

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

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

Так что, если вы видите узел1, узел2, оператор. Вы создаете новый узел 

   Operator
   /     \
  node1   node2

и поместите его обратно в стек.

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

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

RPN для этого kiwis oranges apples AND OR

Теперь пройдитесь, сохраняя стек.

Сделать узел из киви пуш в стек. Узел из апельсинов толкает в стек. То же самое с яблоками.

Итак, стек 

Node:Apples
Node:Oranges
Node:Kiwis

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

Вы извлекаете два верхних из стека и создаете новый узел с AND в качестве родителя.

Узел: AND, [Узел: Яблоки, Узел: Апельсины]

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

       AND
     /    \
  Apples  Oranges

Теперь поместите этот узел в стек.

Так что стек 

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

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

           OR 
         /   \
       AND   Kiwis
     /    \
  Apples  Oranges

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

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

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

...