Собсно как заставить машину делать сабж? Например есть выражение: 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 -- он коммерческий, и быть может имеет более дружественный интерфейс установки/использования.
