Алгоритм удаления лишних скобок из логического выражения

Question

У меня есть логическое выражение в префиксной записи. Скажем так or and A B or or C D E, Когда я преобразую его в инфиксную запись, я получаю((A and B) or ((C or D) or E)), Я хочу уменьшить это до (A and B) or C or D or E, Должен ли я уменьшить инфиксную нотацию или проще получить сокращенную формулу из префиксной нотации. Какие алгоритмы я должен использовать?

Answer 1

Paranthesis может быть удален в выражении X % (X1 ? X2 ? .. ? Xn) % X(n+1) где Xi - это выражение в скобках или логическое значение "?" и "%" являются операторами, если и только если каждый "?" оператор имеет приоритет выше или равен оператору "%".

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

Это превращается в картографическую проблему. Постфиксная запись облегчает удаление скобок. Перевод между префиксной, инфиксной и постфиксной нотацией тривиален.