Стратегии для упрощения математических выражений - PullRequest
Новая
       24

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

62 голосов
/ 24 сентября 2011

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

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

Что выражается в виде этого дерева:

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

"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 th от 42 до степени a th ) равен 42?

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

Ответы [ 6 ]

84 голосов
/ 25 сентября 2011

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

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

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

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

11 голосов
/ 24 сентября 2011

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

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

8 голосов
/ 24 сентября 2011

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

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

2 голосов
/ 24 сентября 2011

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

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

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

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

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

0 голосов
/ 24 сентября 2011

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

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

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

0 голосов
/ 24 сентября 2011

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

...