Построение системы компьютерной алгебры

Question

Я создаю CAS (систему компьютерной алгебры) на PHP, но сейчас я застрял.Я использую этот веб-сайт .

Теперь я написал токенизатор.Он преобразует следующее уравнение:

общий

к этому:

общий

(где группа - это еще один набор токенов).Как я могу упростить это уравнение?Да, я знаю, что вы можете сделать: добавить X-вары, но они находятся в подгруппе.Какой лучший метод я могу использовать для обработки этих токенов?

Answer 1

Следующим действительно полезным шагом было бы создание дерева синтаксического анализа:

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

общий

Обратите внимание, что эта грамматика не обрабатывает синтаксис кода 2x, но ее должно быть легко добавить.

Обратите внимание на умное использование рекурсии в правилах грамматики. primary захватывает только переменные, числа и выражения в скобках и останавливается, когда встречается с оператором. multiplicative анализирует одно или несколько выражений primary, разделенных знаками *, но останавливается, когда встречается со знаком + или -. additive анализирует одно или несколько выражений multiplicative, разделенных + и -, но останавливается, когда встречается с ). Следовательно, схема рекурсии определяет приоритет операторов.

Реализовать прогнозирующий синтаксический анализатор с помощью рукой, как я сделал ниже ( см. полный пример на ideone.com ):

общий

Итак, теперь у вас есть прекрасное дерево синтаксического анализа и даже красивая картинка к нему. Что теперь? Ваша цель (на данный момент) может состоять в том, чтобы просто объединить термины для получения результата в форме:

общий

Я оставлю это вам. Наличие дерева синтаксического анализа должно упростить задачу.

Answer 2

PHP хорош для строк, чисел и массивов. Но это плохой язык для реализации манипуляций с символьными формулами, потому что в нем нет собственного механизма для обработки «символьных выражений», для которых вам действительно нужны деревья. Да, вы можете реализовать всю эту технику. Сложнее выполнять алгебраические манипуляции . Это довольно большая работа, если вы хотите создать что-то полусложное. В идеале вы хотите, чтобы оборудование помогало вам писать преобразования напрямую и легко.

Например, как вы будете реализовывать произвольные правила алгебры? Ассоциативность и коммутативность? Термин «сопоставление на расстоянии»?, Например,

родовое слово

Вы можете посмотреть, как можно реализовать простой CAS с помощью нашего < a href="http://www.semanticdesigns.com/Products/DMS/ProgramTransformation.html" rel="nofollow"> система преобразования программ DMS . DMS имеет встроенные сложные математические конструкции, такие как коммутативность и ассоциативность, и вы можете явно писать правила алгебры для работы с символьными формулами.

Answer 3

Книга Компьютерная алгебра и символьные вычисления: математические методы Джоэла С. Коэна описывает алгоритм автоматического упрощения алгебраических выражений.

Этот алгоритм используется в библиотеке компьютерной алгебры Symbolism для C #.Следуя вашему примеру, следующая программа C #:

общий

отображает на консоли следующее:

общий