Как реализовать вычисление булевой функции на Java?

Question

[goshan_p]

Нужно написать так называемый логический калькулятор. На входе: строка вида " A&(B|C<=>A) " Может содержать все возможные операторы От Отрицания до Стрелки Пирса и Штриха Шеффера. На выходе: Таблица истинности. Я еще мало знаком с сложными структурами вроде Деревьев. Посоветуйте алгоритм для вычисления таких выражений. В голове несколько вариантов разбиения строки и вычисления, но все они кажутся не оптимальными. Расскажите, как бы это сделали вы.

Answer 1

[Евгений Шатунов]

Тебе поможет польская нотация, синтаксическое дерево и синтаксический анализ.

Я бы сделал так.
Прохожу по входной строке слева направо, разбивая ее на лексемы (токены, символы). Правило разбиения такое: если символ под кареткой просмотра является буквой - это операнд, иначе пробуем распознать оператор.
Далее, получив список лексем, я прошелся бы по нему с целью построения дерева операций (польская нотаця, не забывай!). Этот шаг даст мне список операций и операндов. Дерево всегда будет бинарным, даже если там будет унарная операция, это все равно лишь один узел дерева.
Далее я бы составил таблицу значений операндов и вычислил бы по ней значение получившегося дерева операций.

Тебе может помочь вот этот репозиторий:
https://github.com/FrankStain/c-script

И, в частоности, вот этот код:
https://github.com/FrankStain/c-script/blob/master...

Это Object Pascal, но не стоит его чураться. Почитай, покури.

Вноси уточнения в комментах, я буду дополнять свой ответ.

Comments

[goshan_p]

Спасибо. Очень благодарен вам.