Блог

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

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

Например:
если у меня есть следующая формула a * (b * c) a - c
И пользователь выбрал эту подформулу a * (b * c)
А также выбрано это правило преобразования X * ( Y * Z ) ≡ Y * ( X * Z)

Тогда ожидаемый результат должен быть b * ( a * c ) a - c

Существует ли алгоритм, который мог бы выполнить это преобразование, даже если в выражении / правиле есть скобки?

То, о чем вы хотите узнать, — это «системы преобразования программ» (PTS).
Эти инструменты принимают исходный код и явные «правила», которые сообщают ему, как манипулировать кодом. (Комментарий Rici — это очень краткое описание технологии, используемой для реализации PTS.)

Использование произвольных правил, вероятно, приведет к бессмыслице. То, что люди склонны писать, — это правила, которые сохраняют семантику программы. Но хороший PTS примет любые правила, которые вы предоставите, и применит их. PTS rules == «алгоритм» OP.

«Формулы» являются подмножеством «программ», поэтому PTS, который может преобразовывать код, также может преобразовывать формулы.

Полностью проработанный пример PTS, сконфигурированный с правилами для решения алгебры и некоторых простых исчислений, см. В Моем примере алгебры как домена DMS. DMS — это коммерческая PTS, которую я разрабатывал и создавал в течение последних 23 лет.