Есть ли алгоритм для преобразования общей арифметической формулы в другую с использованием произвольных правил?

Question

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

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

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

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

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

Answer 1

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

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

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

Для полностью проработанного примераPTS, настроенного с правилами для решения алгебры и некоторого простого исчисления, см. мой пример Алгебра как область DMS .DMS - это коммерческий PTS, который я разработал и построил за последние 23 года.