Стратегии упрощения математических выражений

Ответ 1

Вероятно, вы захотите внедрить систему перезаписи терминов . Что касается базовой математики, посмотрите WikiPedia.

Структура модуля перезаписи терминов

Так как я недавно реализовал решение...

• Сначала подготовьте класс CExpression, который моделирует структуру вашего выражения.

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

• Затем реализуем класс CRule. Основной метод applyRule(CExpression, CRule) пытается сопоставить правило с любым применимым подвыражением выражения. Если он совпадает, верните результат.

• Завершить, реализовать класс CRuleSet, который представляет собой просто набор объектов CRule. Основной метод reduce(CExpression) применяет набор правил до тех пор, пока не может применяться больше правил, а затем возвращается сокращенное выражение.

• Кроме того, вам нужен класс CBindingEnvironment, который сопоставляет уже согласованные символы с согласованными значениями.

Попробуйте переписать выражение в нормальную форму

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

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

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

• В конце концов, это буквальное значение может отображаться как можно правее и может быть оценено как часть полностью литерального выражения.

Когда оценивать полностью буквальное выражение

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

   x * ( 1 / 3 )

который уменьшился бы до

   x * 0.333333333333333333

Теперь предположим, что x заменено на 3. Это даст что-то вроде

   0.999999999999999999999999

Таким образом, ожидаемая оценка возвращает немного неправильное значение.

С другой стороны, если вы держите (1/3) и сначала замените x на 3

   3 * ( 1 / 3 )

правило перезаписи дало бы

   1

Таким образом, может быть полезно оценить полностью буквальное выражение в конце.

Примеры правил перезаписи

Вот как мои правила появляются внутри приложения: Символы _1, _2,... соответствуют любому подвыражению:

addRule( new TARuleFromString( '0+_1',   // left hand side  :: pattern
                               '_1'      // right hand side :: replacement
                             ) 
       );

или немного сложнее

addRule( new TARuleFromString( '_1+_2*_1', 
                               '(1+_2)*_1' 
                             ) 
       );

Некоторые специальные символы соответствуют только специальным подвыражениям. Например. _Literal1, _Literal2,... соответствуют только буквальным значениям:

addRule( new TARuleFromString( 'exp(_Literal1) * exp(_Literal2 )', 
                               'exp( _Literal1 + _Literal2 )' 
                             ) 
       );

Это правило перемещает нелитеральное выражение влево:

addRule( new TARuleFromString( '_Literal*_NonLiteral', 
                               '_NonLiteral*_Literal' 
                             ) 
       );

Любое имя, начинающееся с символа '_', является переменной шаблона. Хотя система соответствует правилу, она хранит стек назначений уже согласованных символов.

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

В моей реализации я не сохраняю промежуточных выражений напрямую. Я сохраняю массив хешей MD5() промежуточного выражения.

Набор правил в качестве отправной точки

Вот набор правил для начала работы:

            addRule( new TARuleFromString( '0+_1', '_1' ) );
            addRule( new TARuleFromString( '_Literal2=0-_1', '_1=0-_Literal2' ) );
            addRule( new TARuleFromString( '_1+0', '_1' ) );

            addRule( new TARuleFromString( '1*_1', '_1' ) );
            addRule( new TARuleFromString( '_1*1', '_1' ) );

            addRule( new TARuleFromString( '_1+_1', '2*_1' ) );

            addRule( new TARuleFromString( '_1-_1', '0' ) );
            addRule( new TARuleFromString( '_1/_1', '1' ) );

            // Rate = (pow((EndValue / BeginValue), (1 / (EndYear - BeginYear)))-1) * 100 

            addRule( new TARuleFromString( 'exp(_Literal1) * exp(_Literal2 )', 'exp( _Literal1 + _Literal2 )' ) );
            addRule( new TARuleFromString( 'exp( 0 )', '1' ) );

            addRule( new TARuleFromString( 'pow(_Literal1,_1) * pow(_Literal2,_1)', 'pow(_Literal1 * _Literal2,_1)' ) );
            addRule( new TARuleFromString( 'pow( _1, 0 )', '1' ) );
            addRule( new TARuleFromString( 'pow( _1, 1 )', '_1' ) );
            addRule( new TARuleFromString( 'pow( _1, -1 )', '1/_1' ) );
            addRule( new TARuleFromString( 'pow( pow( _1, _Literal1 ), _Literal2 )', 'pow( _1, _Literal1 * _Literal2 )' ) );

//          addRule( new TARuleFromString( 'pow( _Literal1, _1 )', 'ln(_1) / ln(_Literal1)' ) );
            addRule( new TARuleFromString( '_literal1 = pow( _Literal2, _1 )', '_1 = ln(_literal1) / ln(_Literal2)' ) );
            addRule( new TARuleFromString( 'pow( _Literal2, _1 ) = _literal1 ', '_1 = ln(_literal1) / ln(_Literal2)' ) );

            addRule( new TARuleFromString( 'pow( _1, _Literal2 ) = _literal1 ', 'pow( _literal1, 1 / _Literal2 ) = _1' ) );

            addRule( new TARuleFromString( 'pow( 1, _1 )', '1' ) );

            addRule( new TARuleFromString( '_1 * _1 = _literal', '_1 = sqrt( _literal )' ) );

            addRule( new TARuleFromString( 'sqrt( _literal * _1 )', 'sqrt( _literal ) * sqrt( _1 )' ) );

            addRule( new TARuleFromString( 'ln( _Literal1 * _2 )', 'ln( _Literal1 ) + ln( _2 )' ) );
            addRule( new TARuleFromString( 'ln( _1 * _Literal2 )', 'ln( _Literal2 ) + ln( _1 )' ) );
            addRule( new TARuleFromString( 'log2( _Literal1 * _2 )', 'log2( _Literal1 ) + log2( _2 )' ) );
            addRule( new TARuleFromString( 'log2( _1 * _Literal2 )', 'log2( _Literal2 ) + log2( _1 )' ) );
            addRule( new TARuleFromString( 'log10( _Literal1 * _2 )', 'log10( _Literal1 ) + log10( _2 )' ) );
            addRule( new TARuleFromString( 'log10( _1 * _Literal2 )', 'log10( _Literal2 ) + log10( _1 )' ) );

            addRule( new TARuleFromString( 'ln( _Literal1 / _2 )', 'ln( _Literal1 ) - ln( _2 )' ) );
            addRule( new TARuleFromString( 'ln( _1 / _Literal2 )', 'ln( _Literal2 ) - ln( _1 )' ) );
            addRule( new TARuleFromString( 'log2( _Literal1 / _2 )', 'log2( _Literal1 ) - log2( _2 )' ) );
            addRule( new TARuleFromString( 'log2( _1 / _Literal2 )', 'log2( _Literal2 ) - log2( _1 )' ) );
            addRule( new TARuleFromString( 'log10( _Literal1 / _2 )', 'log10( _Literal1 ) - log10( _2 )' ) );
            addRule( new TARuleFromString( 'log10( _1 / _Literal2 )', 'log10( _Literal2 ) - log10( _1 )' ) );


            addRule( new TARuleFromString( '_Literal1 = _NonLiteral + _Literal2', '_Literal1 - _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_Literal1 = _NonLiteral * _Literal2', '_Literal1 / _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_Literal1 = _NonLiteral / _Literal2', '_Literal1 * _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_Literal1 =_NonLiteral - _Literal2',  '_Literal1 + _Literal2 = _NonLiteral' ) );

            addRule( new TARuleFromString( '_NonLiteral + _Literal2 = _Literal1 ', '_Literal1 - _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_NonLiteral * _Literal2 = _Literal1 ', '_Literal1 / _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_NonLiteral / _Literal2 = _Literal1 ', '_Literal1 * _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_NonLiteral - _Literal2 = _Literal1',  '_Literal1 + _Literal2 = _NonLiteral' ) );

            addRule( new TARuleFromString( '_NonLiteral - _Literal2 = _Literal1 ', '_Literal1 + _Literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_Literal2 - _NonLiteral = _Literal1 ', '_Literal2 - _Literal1 = _NonLiteral' ) );

            addRule( new TARuleFromString( '_Literal1 = sin( _NonLiteral )', 'asin( _Literal1 ) = _NonLiteral' ) );
            addRule( new TARuleFromString( '_Literal1 = cos( _NonLiteral )', 'acos( _Literal1 ) = _NonLiteral' ) );
            addRule( new TARuleFromString( '_Literal1 = tan( _NonLiteral )', 'atan( _Literal1 ) = _NonLiteral' ) );

            addRule( new TARuleFromString( '_Literal1 = ln( _1 )', 'exp( _Literal1 ) = _1' ) );
            addRule( new TARuleFromString( 'ln( _1 ) = _Literal1', 'exp( _Literal1 ) = _1' ) );

            addRule( new TARuleFromString( '_Literal1 = _NonLiteral', '_NonLiteral = _Literal1' ) );

            addRule( new TARuleFromString( '( _Literal1 / _2 ) = _Literal2', '_Literal1 / _Literal2 = _2 ' ) );

            addRule( new TARuleFromString( '_Literal*_NonLiteral', '_NonLiteral*_Literal' ) );
            addRule( new TARuleFromString( '_Literal+_NonLiteral', '_NonLiteral+_Literal' ) );

            addRule( new TARuleFromString( '_Literal1+(_Literal2+_NonLiteral)', '_NonLiteral+(_Literal1+_Literal2)' ) );
            addRule( new TARuleFromString( '_Literal1+(_Literal2+_1)', '_1+(_Literal1+_Literal2)' ) );

            addRule( new TARuleFromString( '(_1*_2)+(_3*_2)', '(_1+_3)*_2' ) );
            addRule( new TARuleFromString( '(_2*_1)+(_2*_3)', '(_1+_3)*_2' ) );

            addRule( new TARuleFromString( '(_2*_1)+(_3*_2)', '(_1+_3)*_2' ) );
            addRule( new TARuleFromString( '(_1*_2)+(_2*_3)', '(_1+_3)*_2' ) );

            addRule( new TARuleFromString( '(_Literal * _1 ) / _Literal', '_1' ) );
            addRule( new TARuleFromString( '(_Literal1 * _1 ) / _Literal2', '(_Literal1 * _Literal2 ) / _1' ) );

            addRule( new TARuleFromString( '(_1+_2)+_3', '_1+(_2+_3)' ) );
            addRule( new TARuleFromString( '(_1*_2)*_3', '_1*(_2*_3)' ) );

            addRule( new TARuleFromString( '_1+(_1+_2)', '(2*_1)+_2' ) );

            addRule( new TARuleFromString( '_1+_2*_1', '(1+_2)*_1' ) );

            addRule( new TARuleFromString( '_literal1 * _NonLiteral = _literal2', '_literal2 / _literal1 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_literal1 + _NonLiteral = _literal2', '_literal2 - _literal1 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_literal1 - _NonLiteral = _literal2', '_literal1 - _literal2 = _NonLiteral' ) );
            addRule( new TARuleFromString( '_literal1 / _NonLiteral = _literal2', '_literal1 * _literal2 = _NonLiteral' ) );

Сделать правила первоклассными выражениями

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

Разбор выражений (или более общих: языки)

Для приложений Cocoa/OBjC, Dave DeLong DDMathParser является идеальным кандидатом для синтаксического анализа математических выражений.

Для других языков наши старые друзья Lex и Yacc или более новый GNU Bison может помочь.

Более молодой и богатый набор готовых к использованию синтаксических файлов, ANTLR - это современный генератор парсеров на основе Java. Помимо чисто командной строки, ANTLRWorks предоставляет интерфейс GUIдля создания и отладки парсеров на основе ANTLR. ANTLR генерирует грамматики для различных языков хоста, например JAVA, C, Python, PHP или С#. В настоящее время среда выполнения ActionScript отключена.

Если вы хотите научиться разбирать выражения (или вообще языки) снизу вверх, я бы предложил этот бесплатный текст книги от Niklaus Wirth (или немецкая книжная версия), известный изобретатель Паскаля и Модулы-2.

Ответ 2

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

Вы можете найти читаемое введение, как это делается (оценка на основе правил), например. для Mathematica.

Ответ 3

Вы хотите создать CAS (вычислительная алгебра система), и тема настолько широка, что есть целая область исследования, посвященная этому. Это означает, что есть несколько книг, которые, вероятно, ответят на ваш вопрос лучше, чем SO.

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

Ответ 4

Я считаю, что вам нужно "перебрать силу" таких деревьев.

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

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

Умножения могут быть представлены как дополнения, поэтому одно правило может заключаться в том, что a - a отменяет себя: 2a-a = a + a-a

Другим правилом было бы сначала размножить все деления, потому что это фракции. Пример:

1/2 + 3/4 Откройте все деления, а затем умножьте каждую фракцию на делитель с обеих сторон всех других фракций

4/8 + 6/8 Тогда все элементы имеют один и тот же делитель, и поэтому унифицированный (4 + 6)/8 = 10/8

Наконец, вы найдете самый высокий общий делитель между верхним и нижним 5/4

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

Все это время вы проверите снова свои правила ярлыков, чтобы обнаружить такие упрощения. Чтобы знать, что применяется правило, вам, вероятно, придется либо попробовать все перестановки поддерева. Например. Правило a-a также будет применяться для -a + a. Может быть a + b-a.

Просто некоторые мысли, надеюсь, что вы получите некоторые идеи...

Ответ 5

На самом деле вы вообще не можете этого сделать, потому что, хотя они одинаковы математически, в арифметике компьютера может не совпадать. Например, -MAX_INT undefined, поэтому -% a =/=% a. Аналогично для поплавков вам необходимо иметь дело с NaN и Inf соответствующим образом.

Ответ 6

Мой наивный подход состоял бы в том, чтобы иметь некоторую структуру данных с инверсиями каждой функции (т.е. divide и multiply). Вам, очевидно, потребуется дополнительная логика, чтобы убедиться, что они фактически инвертированы, поскольку умножение на 3, а затем деление на 4 на самом деле не является обратным.

Хотя это примитивно, я думаю, что это достойный первый проход в проблеме и решит многие случаи, которые вы отметили в своем вопросе.

Я с нетерпением жду, чтобы ваше полное решение и страх в страхе - это математический блеск:)