Как сформулировать алгоритм для визуального редактирования запросов?

Question

[Mercury13]

Есть самодельный визуальный редактор запросов. Запрос представляет собой линейный список из условий и логических операций (три варианта: AND, OR и () AND ()). У первой строчки операции нет. () AND () — это такой AND, приоритет которого ниже даже OR.

Вполне реальный запрос, придуманный «в поле».

группа = 'A'
AND хитрый параметр < 70%
OR группа = 'B'
AND хитрый параметр < 40%
OR группа = 'C'
AND хитрый параметр < 20%
() AND () поставщик = 'первый'
OR поставщик = 'второй'

Эквивалентное условие будет:

((г='A' & хп < 70%) | (г='B' & хп < 40%) | (г='C' & хп < 20%)) & (п = 'первый' | п = 'второй')

Три задачи.
1. Вот у нас этот запрос лежит в визуальном редакторе. Расставить автоматом отступы так, чтобы была понятна логика. Как-то так.

    группа = 'A'
    AND хитрый параметр < 70%
  OR группа = 'B'
    AND хитрый параметр < 40%
  OR группа = 'C'
    AND хитрый параметр < 20%
() AND () поставщик = 'первый'
  OR поставщик = 'второй'

Пока наклёвывается алгоритм: у приоритетного AND отступ 0, у OR 1, у AND 2, у первого пункта без операции — такой же, как у второго. Остаётся только сократить отступы, если нет приоритетного AND.

2. Превратить этот линейный список в план исполнения запроса. Что-то вроде этого.

1. группа = 'A': +2, −3   // при срабатывании GOTO 2, при неудаче — GOTO 3.
2. хитрый параметр < 70%: +7, −3
3. группа = 'B': +4, −5
4. хитрый параметр < 40%: +7, −5
5. группа = 'C': +6, −FALSE      // при срабатывании GOTO 6, при несрабатывании — неудача
6. хитрый параметр < 40%: +7, −FALSE
7. поставщик = 'первый': +TRUE, −8
8. поставщик = 'второй': +TRUE, −FALSE

3. А теперь, представьте себе, мы ввели такое.

группа = 'A'
AND хитрый_параметр < 70%
OR группа = 'B'
AND хитрый параметр < 40%
OR группа = 'C'
AND хитрый параметр < 20%
() AND ()           (дырка)
AND поставщик = 'первый'
OR поставщик = 'второй'

Считаем, что дырка представляет собой тождественное TRUE.

Как преобразовать запрос в эквивалентный, но без дырок? Вместо AND поставить наименее приоритетный из ()AND() и AND?

Answer 1

[Mercury13]

С вопросом 3 оказалось всё одновременно просто и сложно. Дырка — это НЕ тождественный TRUE, это нечто нейтральное к операциям до или после (что приоритетнее). Если OR — внешняя операция, AND — приоритетная, TRUE/FALSE — соотв. нейтральный элемент, то…
A OR (B AND TRUE) OR C = A OR B OR C, то есть AND уходит
(A AND B) OR (TRUE AND C) = (A AND B) OR C, то есть OR занимает место AND.
Так что действительно получается наименее приоритетный из () AND () и AND.

С вопросом 1 так пока и есть.

С вопросом 2 задача оказалась похожа на алгоритм сортировочной станции. С одной стороны, у нас нет ни скобок, ни префиксных/постфиксных функций, ни правоассоциативных операций.

С другой — для каждого элемента стека мы держим op, firstIndex и lastIndex (индексы начала/конца операнда).
Для первого элемента кидаем (⌀, 1, 1). Или (⌀, 0, 0), если индексы с нуля.
Для второго (AND, 2, 2).
Когда попадается третий (OR, 3, 3), срабатывает условие, и мы делаем операцию «сброс AND», состоящую из трё1х вещей:
1. Для первого lastIndex в случае TRUE делаем переход на второе firstIndex.
2. Где-то записываем: у первого lastIndex переход в случае FALSE будет таким же, как и у второго lastIndex.
3. Объединяем эти два элемента, присвоив второй lastIndex первому элементу.
Ну и добавляем наш (OR, 3, 3) в стек — это делается всегда, независимо от того, сколько раз сработало условие сброса.
Как сбросить OR — думаю, понятно.
Таким образом, теперь наш стек будет такой: (⌀, 1, 2) (OR, 3, 3).
Наш план: (+2 −?) (+? −?) …
Наш список аналогов: (1, 2, FALSE)

Четвёртый элемент уйдёт в стек, пятый вызовет сразу два сброса.
Стек (⌀, 1, 4) (OR, 5, 5).
План: (+2 −?) (+? −3) (+4 −?) (+? −?)…
Наш список аналогов: (1, 2, FALSE), (3, 4, FALSE), (2, 4, TRUE)

Когда список кончится, проводим операцию сброса, пока в стеке не останется (⌀, 1, 8), а затем заполним список аналогов с конца.
Если вопросительный знак всё-таки остался — это будет +TRUE или −FALSE.