Parse user-input, относящийся к поисковым критериям

Question

Я ищу способ разобрать некоторый ввод пользователя. Вход должен показывать, какие поисковые запросы должны выполняться, и как их следует комбинировать.

• 1 и 2
• (3 и 2) ИЛИ 1
• (3 и 2) ИЛИ (1 и 4)
• ((3 или 4) и 1) ИЛИ 2
• и т. д.

Первый пример должен объединить результаты поиска 1 и 2 в формате AND. Второй пример должен объединить результаты поиска 3 и 2 в AND-моде и объединить результаты этой комбинации с результатами поиска 1 в OR-моде. И т.д.

Любые идеи о том, как это сделать?

Answer 1

Просто некоторые вдохновение о том, как создать парсер для общего поиска по ключевому слову ...

Даже если вы помечены на вопрос Java, вот пример searchparser в питоне. Он использует pyparsing, генератор синтаксического анализатора, который берет грамматику и создает код, который может быть запущен для парсинга пользователя.

http://pyparsing.wikispaces.com/file/view/searchparser.py

293 строк кода, включая набор тестов. Может быть, это поможет вам в качестве отправной точки ...

Answer 2

Think вашего «результат» как объект, который предлагает методы и и или, как в следующий интерфейс:

public interface AndOrCapable<T> { 
    public T and(T anOtherResult); 
    public T or(T anOtherResult); 
} 

Затем вы можете перевести пользователя вход в нечто вроде:

Result total = r2.or(r1.and(r3.or(r4))); // your fourth example 

Это просто уточнить понятие - в вашем случае вам нужен динамический оценщик, потому что вы используете пользовательский ввод.

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

Надеюсь, это помогло немного!

Answer 3

Чистым решением было бы написать парсер infix; в Интернете есть несколько примеров кода. В вашем примере может потребоваться более простой алгоритм, поскольку вам не требуется приоритет оператора и т. Д.

В качестве примечания о кодировании: класс StreamTokenizer может помочь вам разобрать входную строку.

Answer 4

В конце реализации (когда у вас есть парсер, организация и выполнение поиска):

1. Что о создании Condition дерева, где Condition объекты могут быть простыми условиями или сложными условиями присоединяющихся 2 простого условием с булевым (IE ANDCondition родительским узлом с детьми RangeCondition и EqualsCondition).

   Затем вы оцениваете верхнюю часть дерева по каждому элементу. Это решение O (mn), где m - количество условий, а n - количество элементов для поиска, но вы можете оптимизировать это, удалив избыточные условия. Это намного быстрее, если первое условие устраняет большинство элементов.

2. Версия 2: назначить уникальный ключ каждому элементу (скажем, индекс массива) и выполнить поиск каждого условия, построив для каждого условия HashSet<Key>. Затем, начиная с наименьшего набора , требуется ключей, удалите или добавьте ключи для каждого условия, пока не получите окончательные результаты. Это может быть быстрее, чем указано выше, в зависимости.

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

Answer 5

JavaCC - хороший инструмент для создания синтаксического анализатора для этого. В качестве альтернативы, если вы можете немного изменить синтаксис, вы можете использовать возможности сценариев с помощью java с помощью интерпретатора схемы, например.

((3 OR 4) AND 1) OR 2 

становится

(OR (AND (OR 3 4) 1) 2) 

Тогда вам просто необходимо реализовать И/ИЛИ