Вы должны сделать 4 шага для достижения своей цели:
1) разобрать выражение, используя «стандартные» (методы не связан с вашей терминологией) синтаксического анализа и производить то, что составляет логическое выражение дерево, представляющее (разобранное) выражение.
2) применять правила булевой алгебры к дереву выражений, чтобы преобразовать его из представления, которое вы не хотите, к тому, которое вы делаете. Ваша «стандартная форма» представляется конъюнктивной нормальной формой (CNF), поэтому вам нужно, чтобы правила распределенной законной алгебры «размножались» над суммами (например, a * (b + c)), чтобы «избавиться от круглых скобок»
3) Затем вам необходимо применить некоторые правила упрощения (например, допуск, аннулирование), чтобы избавиться от лишних членов, например, a * b + a * b + c ==> a * b [a * b * c) и a * b * a '+ b * c ==> b * c [a * .. a' отменяется]. Это всего лишь правила алгебры.
4) PrettyPrint полученный результат выражения в человекообразном формате.
Вы можете написать все это с помощью A) ad hoc ручного кодирования рекурсивного спуска и ad hoc-правила и красивой печати, или B) вы можете получить генератор синтаксического анализатора (ANTLR), чтобы выполнить синтаксический анализ, и выполните правило манипуляции с помощью ad hoc-методов и отпечаток с помощью некоторой помощи, например, строковых шаблонов, или C) вы можете получить инструмент, который выполняет синтаксический анализ, строит деревья, будет применять правила алгебры, которые вы определяете, и имеет встроенную встроенную печать.
Наши DMS Software Reengineering Toolkit делаю случай C приятно. Вы можете увидеть example of applying standard algebra rules that is a direct analog to your problem.
Одной из проблем, которые действительно трудно получить, является обработка ассоциативности и коммутативности в алгебре, например, знание того, что A * B * A 'является «ложным», является следствием правила алгебры X * X' = > false, но вы не можете просто проверить шаблон в правиле алгебры напрямую. Вы должны применять правила алгебры, учитывающие коммутативность. Тот же аргумент для ассоциативности. Одна из вещей, которые DMS прекрасно выполняет, - это для вас, если вы объявите соответствующие операторы для этих свойств. Вы можете увидеть это в примере.
Увы, не кодируется на Java.
Если это логические переменные, то не следует упрощать A * B * B * D до A * B * D? Что вы пробовали? У вас есть синтаксический анализатор для чтения в ваших текущих выражениях или они уже обрабатываются? – Jim
Очевидно, что вы разбираете его, получаете представление, преобразуете это представление и печатаете результат. Что-нибудь более конкретное? Что вы пробовали? Что вы уже сделали? – delnan
Какие упрощения вы должны делать? Предполагая, что * является вашим символом AND и + является вашим символом OR, обратите внимание, что A * B * (A * B + A + B) сводится к A * B. Поскольку оба * и + являются коммутативными, вы можете распечатать стандартную форму в каноническом порядке. Является ли B 'другой переменной, чем B? Это домашнее задание? – Jim