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

у меня есть хорошо сформированное дерево, которое представляет собой математическое выражение. Например, учитывая строку:"1+2-3*4/5", это разбирается в:



subtract(add(1,2),divide(multiply(3,4),5))


который выражается как это дерево:



"1+2-3*4/5"



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



"3*$a/$a" становится divide(multiply(3,$a), $a)



это должно упростить для 3 С $a условия должны отменять друг друга. Вопрос в том, " как я могу распознать это в общем виде?- Как я узнаю это min(3, sin($x)) всегда sin($x)? Как я узнаю это sqrt(pow($a, 2)) и abs($a)? Как я узнаю это nthroot(pow(42, $a), $a) (aе корень из 42 в aе мощность) - это 42?



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

854   6  

6 ответов:

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

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

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

  • Сначала подготовьте класс 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, DDMathParser Дейва Делонга является идеальным кандидатом для синтаксического анализа математических выражений.

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

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

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

78  
2017-05-23 15:26:01

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

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

10  
2011-09-24 19:35:15

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

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

7  
2011-09-24 19:41:41

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

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

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

умножения могут быть представлены как дополнения, поэтому одно правило может заключаться в том, что 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.

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

1  
2011-09-24 20:44:30

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

0  
2011-09-24 19:35:54

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

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

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

0  
2011-09-24 20:29:03

Comments

    Ничего не найдено.
Click here to cancel reply.