Estratégias para simplificar expressões matemáticas

Eu tenho uma tree bem formada que representa uma expressão matemática. Por exemplo, dada a string: "1+2-3*4/5" , isso é analisado em:

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

Qual é expresso como esta tree:

O que eu gostaria de poder fazer é pegar esta tree e reduzi-la o máximo possível. No caso acima, isso é bem simples, porque todos os números são constantes. No entanto, as coisas começam a ficar mais complicadas quando permito incógnitas (denotadas com um $ seguido por um identificador):

"3*$a/$a" torna-se divide(multiply(3,$a), $a)

Isso deve simplificar para 3 , já que os termos $a devem se anular mutuamente. A questão é: “como faço para reconhecer isso de uma maneira genérica?” Como eu reconheço que min(3, sin($x)) sempre será sin($x) ? Como eu reconheço que sqrt(pow($a, 2)) é abs($a) ? Como eu reconheço que nthroot(pow(42, $a), $a) (a raiz de um th de 42 a um poder th ) é 42 ?

Eu percebo que essa pergunta é bem ampla, mas eu tenho batido com a minha cabeça contra isso por um tempo e não encontrei nada satisfatório o suficiente.

Você provavelmente deseja implementar um sistema de reescrita de termos . Em relação à matemática subjacente, dê uma olhada na WikiPedia .

Estrutura de um módulo de reescrita de termo

Desde que eu implementei uma solução recentemente …

  • Primeiro, prepare uma class CExpression, que modela a estrutura da sua expressão.

  • Implemente o CRule , que contém um padrão e uma substituição. Use símbolos especiais como variables ​​de padrão, que precisam ficar vinculados durante a correspondência de padrões e substituídos na expressão de substituição.

  • Em seguida, implemente um CRule class. É o método principal applyRule(CExpression, CRule) tenta corresponder a regra a qualquer subexpressão de expressão aplicável. Caso corresponda, devolva o resultado.

  • Finalmente, implemente uma class CRuleSet , que é simplesmente um conjunto de objects CRule. O principal método reduce(CExpression) aplica o conjunto de regras, desde que não mais regras possam ser aplicadas e, em seguida, retorna a expressão reduzida.

  • Além disso, você precisa de uma class CBindingEnvironment , que mapeia os símbolos já correspondidos para os valores correspondentes.

Tente rewrite a expressão para uma forma normal

Não se esqueça de que essa abordagem funciona até certo ponto, mas provavelmente não é completa. Isso se deve ao fato de que todas as regras a seguir executam reescritas de termos locais.

Para tornar essa lógica de reescrita local mais forte, deve-se tentar transformar expressões em algo que eu chamaria de forma normal. Esta é minha abordagem:

  • Se um termo contiver valores literais, tente mover o termo o mais para a direita possível.

  • Eventualmente, esse valor literal pode aparecer mais à direita e pode ser avaliado como parte de uma expressão totalmente literal.

Quando avaliar a expressão totalmente literal

Uma questão interessante é quando avaliar a expressão totalmente literal. Suponha que você tenha uma expressão

  x * ( 1 / 3 ) 

o que reduziria a

  x * 0.333333333333333333 

Agora suponha que x seja substituído por 3. Isso produziria algo como

  0.999999999999999999999999 

Assim, a avaliação ansiosa retorna um valor ligeiramente incorreto.

No outro lado, se você mantiver (1/3) e primeiro replace x por 3

  3 * ( 1 / 3 ) 

uma regra de reescrita daria

  1 

Assim, pode ser útil avaliar tardiamente a expressão totalmente literal.

Exemplos de regras de reescrita

Veja como minhas regras aparecem dentro do aplicativo: Os símbolos _1, _2, … correspondem a qualquer subexpressão:

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

ou um pouco mais complicado

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

Certos símbolos especiais correspondem apenas a subexpressões especiais. Por exemplo, _Literal1, _Literal2, … correspondem apenas a valores literais:

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

Esta regra move a expressão não literal para a esquerda:

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

Qualquer nome que comece com um ‘_’ é uma variável de padrão. Enquanto o sistema corresponde a uma regra, ele mantém uma pilha de atribuições de símbolos já correspondidos.

Finalmente, não se esqueça de que as regras podem resultar em sequências de substituição não terminadas. Assim, ao reduzir a expressão, lembre o processo, que expressões intermediárias já foram atingidas antes.

Na minha implementação, não salve expressões intermediárias diretamente. Eu mantenho uma matriz de hashes MD5 () de expressão intermediária.

Um conjunto de regras como ponto de partida

Aqui está um conjunto de regras para começar:

  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' ) ); 

Faça regras de expressões de primeira class

Um ponto interessante: Como as regras acima são expressões especiais, que são avaliadas corretamente pelo analisador de expressão, os usuários podem até adicionar novas regras e, assim, aprimorar os resources de reescrita do aplicativo.

Expressões de análise (ou mais gerais: idiomas)

Para aplicativos Cocoa / OBjC , o DDMathParser de Dave DeLong é um candidato perfeito para analisar sintaticamente expressões matemáticas.

Para outros idiomas, nossos velhos amigos Lex & Yacc ou o mais novo GNU Bison podem ajudar.

Muito mais jovem e com um enorme conjunto de arquivos de syntax prontos para usar , o ANTLR é um moderno gerador de analisadores baseado em Java. Além do uso puramente de linha de comando, o ANTLRWorks fornece uma interface GUI para construir e depurar analisadores baseados em ANTLR. O ANTLR gera gramáticas para várias linguagens do host , como JAVA, C, Python, PHP ou C # . O tempo de execução do ActionScript está atualmente quebrado .

Caso você queira aprender como analisar expressões (ou idiomas em geral) de baixo para cima, eu proponho o texto deste livro gratuito de Niklaus Wirth (ou a edição alemã do livro ), o famoso inventor de Pascal e Modula. -2.

Esta tarefa pode se tornar bastante complicada (além da transformação mais simples). Essencialmente, é isso que o software de álgebra faz o tempo todo.

Você pode encontrar uma introdução legível como isso é feito (avaliação baseada em regras), por exemplo, para o Mathematica .

Você está querendo construir um CAS (sistema de álgebra computacional) e o tópico é tão amplo que existe um campo de estudo inteiro dedicado a ele. O que significa que há alguns livros que provavelmente responderão à sua pergunta melhor que o SO.

Eu sei que alguns sistemas constroem trees que reduzem as constantes primeiro e então colocam a tree em uma forma normalizada e então usam um grande database de fórmulas comprovadas / conhecidas para transformar o problema em alguma outra forma.

Eu acredito que você tem que “força bruta” tais trees.

Você terá que formular algumas regras que descrevam possíveis simplificações. Então você deve percorrer a tree e procurar as regras aplicáveis. Como algumas simplificações podem levar a resultados mais simples do que outras, você terá que fazer uma coisa semelhante para encontrar o caminho mais curto em um plano de metrô: experimente todas as possibilidades e classifique os resultados por alguns critérios de qualidade.

Como o número de tais cenários é finito, você pode descobrir automaticamente as regras de simplificação experimentando todas as combinações de operadores e variables ​​e novamente ter um algoritmo genético que verifica que a regra não foi encontrada antes e que simplifica a input .

As multiplicações podem ser representadas como acréscimos, portanto, uma regra pode ser que a – a se anula: 2a-a = a + aa

Outra regra seria primeiro multiplicar todas as divisões porque elas são frações. Exemplo:

1/2 + 3/4 Descubra todas as divisões e multiplique cada fração com o divisor em ambos os lados de todas as outras frações

4/8 + 6/8 Então todos os elementos têm o mesmo divisor e o mesmo pode ser unificado para (4 + 6) / 8 = 10/8

Finalmente você encontra o maior divisor comum entre o topo e o fundo 5/4

Aplicada à sua tree, a estratégia seria trabalhar de baixo para cima, simplificando cada multiplicação, convertendo-a em acréscimos. Então simplificando cada adição como as frações

Enquanto você verifica as regras do seu atalho, descobre essas simplificações. Para saber que uma regra se aplica, você provavelmente terá que testar todas as permutações de uma subtree. Por exemplo, a regra aa também se aplica a -a + a. Pode haver um + ba.

Apenas alguns pensamentos, espero que te dê algumas ideias …

Na verdade, você não pode, em geral, fazer isso porque, embora sejam os mesmos matematicamente, talvez não seja o mesmo na aritmética computacional. Por exemplo, -MAX_INT é indefinido, então -% a = / =% a. Da mesma forma para carros alegóricos, você tem que lidar com NaN e Inf apropriadamente.

Minha abordagem ingênua seria ter algum tipo de estrutura de dados com inversos de cada function (isto é, divide e multiply ). Você obviamente precisaria de mais lógica para se certificar de que eles são realmente inversos, já que multiplicar por 3 e, em seguida, dividir por 4 não é realmente um inverso.

Embora isso seja primitivo, acho que é um primeiro passo decente para o problema e resolveria muitos dos casos que você observou em sua pergunta.

Estou ansioso para ver a sua solução completa e olhando com admiração é o brilho da matemática 🙂