Упрощение выражений

Собсно как заставить машину делать сабж?

Например есть выражение: a+b-a+a+b

Из курса начальной церковно-приходской школы я знаю что это можно упростить до a+2b

Но как это обьяснить машине? Изобретать велосипед неохота - наверняка на эту тему писалась неодна диссертация

any ideas?

 

Dr.Golova



То что тебе нужно называется "symbolic calculation" и встроенно в любую algebra system. Так как пока непонятно, что тебя конкретно интересует(операции,сложность,язык и т.д), то могу только отправить в Google. Пара примеров, откуда наверное можно взять код:

gTybalt

Math::Symbolic - Symbolic math for Perl

 

по идее это довольно просто для

этого сначала ракрываем ( ну там знаки меняем если нужно) скобки , потом заносим в список все встретившиеся символы со своими знаками , потом складываем одинаковые символы учитавая знак , и заносим результат в новый список

потом список распечатываем







типа так





1)+a,-a,+a,+b,+b

2)+a-a+a = +a

вставляем в новый список +a

+b+b= +2b

вставляем в новый список +2b



получаем список +a,+2b



распечатываем - получаем a+2b





сумноржением тоже можно придумать , например разложить на слагаемые

насчет деления, не приходит в голову ничего кроме коэффициентов

 

> что тебя конкретно интересует



Конкретнее - a, b, c и т.д. - некие эфемерные неделимые обьекты, к которым многократно могут быть применены некоторые действия, необязательно математические (например "выделить"/"отменить выделение"), и действия необязательно из двух состояний как в примере с +/-. Хочется выкинуть как можно больше (необязатльно все) лишних/взаимоисключающих действий.

 

Dr.Golova

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

 

Преобразование к обратной польской нотации может помочь + прикрутить простейший калькулятор для вычисления коэффициентов a, b, c и т.д. при выталкивании из стэка.

 

> Преобразование к обратной польской нотации



ИМХО это для расстановки скобок, а у меня все действия линейно друг за другом. Складывается впечатление что если я стэки на каждую операцию то будет мне щастье, но помойму это извращение и должен быть алгоритм пограмотнее.

 

не только для скобок, но и для разных приоритетов операций. Если приоритеты не важны, мона просто парсить строчку и считать символы a, b, c и т.д.

 

Если программа делается только для себя, то проще всего делать на функциональных языках типа ЛИСП или Пролог. Там получается очень короткий и понятный код с учетом приоритетов и скобок:

http://www.csc.vill.edu/~dmatusze/resources/lisp/lisp-example.html



Иначе нужно писать на обычных процедурных языках (деревья синтаксического разбора, стеки и все такое).

 

есть maxima вся из себя написанная на LISP, которая предназначена для всяких символических вычислений...

Она имеет ряд функций упрощения, типа превратить в произведение или в сумму для разных типов выражений. Плюс функцию expand которая наоборот, стремится раскрыть все скобки/функции, и оставить только сумму степеней переменных с коэффициентами. В общем на относительно простых выражениях, maxima упрощает правильно.

Я бы на месте Dr.Golova научился заставлять maxima делать то что надо (то есть написал бы скрипт), а потом бы думал сколько стеков надо.



Хотя если выражение -- это многочлен (а не произвольное математическое выражение), то нужно иметь всего один стек -- стек для обработки скобочных выражений. А складывать в такой стек надо многочлены. Быть может это было описано у Кнута, или мне только кажется (но про работу с многочленами он что-то писал -- факт)



ЗЫ вместо maxima, наверное можно пользовать Maple -- он коммерческий, и быть может имеет более дружественный интерфейс установки/использования.