Analisador de equação (expressão) com precedência?

Desenvolvi um analisador de equações usando um algoritmo de pilha simples que manipulará operadores binários (+, -, &, *, /, etc), operadores unários (!) E parênteses.

No entanto, usar esse método me deixa com tudo o que tem a mesma precedência – ele é avaliado da esquerda para a direita, independentemente do operador, embora a precedência possa ser imposta usando parênteses.

Então, agora “1 + 11 * 5” retorna 60, não 56 como se poderia esperar.

Embora isso seja adequado para o projeto atual, quero ter uma rotina de uso geral que possa ser usada em projetos posteriores.

Editado para maior clareza:

O que é um bom algoritmo para analisar equações com precedência?

Estou interessado em algo simples de implementar e entender que posso me codificar para evitar problemas de licenciamento com o código disponível.

Gramática:

Eu não entendo a questão gramatical – escrevi isso à mão. É simples o suficiente para não ver a necessidade de YACC ou Bison. Eu apenas preciso calcular strings com equações como “2 + 3 * (42/13)”.

Língua:

Estou fazendo isso em C, mas estou interessado em um algoritmo, não em uma solução específica de idioma. C é baixo o suficiente para ser fácil de converter para outro idioma em caso de necessidade.

Exemplo de código

Eu postei o código de teste para o analisador de expressões simples que eu estava falando acima. Os requisitos do projeto foram alterados e, portanto, nunca precisei otimizar o código para desempenho ou espaço, pois ele não foi incorporado ao projeto. Está na forma verbosa original e deve ser prontamente compreensível. Se eu fizer algo mais em termos de precedência do operador, provavelmente escolherei o hack da macro porque ele combina com o resto do programa na simplicidade. Se eu usar isso em um projeto real, vou procurar um analisador mais compacto / rápido.

Questão relacionada

Design inteligente de um analisador matemático?

-Adão

O jeito difícil

Você quer um analisador de descida recursivo .

Para obter precedência, você precisa pensar recursivamente, por exemplo, usando sua string de amostra,

1+11*5 

para fazer isso manualmente, você teria que ler o 1 , então ver o mais e iniciar uma nova “session” de análise recursiva começando com 11 … e certifique-se de analisar o 11 * 5 em seu próprio fator, gerando uma análise. tree com 1 + (11 * 5) .

Isso tudo parece tão doloroso até para tentar explicar, especialmente com a impotência adicional de C. Veja, depois de analisar o 11, se o * fosse realmente um +, você teria que abandonar a tentativa de fazer um termo e, em vez disso, analisar o 11 como um fator. Minha cabeça já está explodindo. É possível com a estratégia decente recursiva, mas existe uma maneira melhor …

O caminho fácil (certo)

Se você usa uma ferramenta GPL como Bison, provavelmente não precisa se preocupar com problemas de licenciamento, já que o código C gerado por bison não é coberto pela GPL (IANAL, mas tenho certeza que as ferramentas GPL não forçam a GPL em código gerado / binários, por exemplo, a Apple compila o código como, digamos, Aperture com GCC e eles vendem sem ter que GPL disse o código).

Baixe Bison (ou algo equivalente, ANTLR, etc.).

Geralmente, há algum código de amostra no qual você pode executar o bison e obter o código C desejado que demonstra essa calculadora de quatro funções:

http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html

Veja o código gerado e veja que isso não é tão fácil quanto parece. Além disso, as vantagens de usar uma ferramenta como o Bison são: 1) você aprende alguma coisa (especialmente se você lê o livro do Dragão e aprende sobre gramáticas), 2) você evita o NIH tentando reinventar a roda. Com uma ferramenta real de gerador de analisadores, você realmente tem a esperança de expandir mais tarde, mostrando a outras pessoas que você sabe que os analisadores são o domínio das ferramentas de análise.


Atualizar:

As pessoas aqui ofereceram muitos conselhos sólidos. Meu único aviso contra pular as ferramentas de análise ou simplesmente usar o algoritmo Shunting Yard ou um parser decursivo recursivo é que as pequenas linguagens de brinquedo podem um dia tornar-se grandes linguagens reais com funções (senco, cos, log) e variables, condições e rotações.

O Flex / Bison pode muito bem ser um exagero para um intérprete pequeno e simples, mas um avaliador + analisador pode causar problemas quando as alterações precisarem ser feitas ou os resources precisarem ser adicionados. Sua situação irá variar e você precisará usar seu julgamento; simplesmente não castigue outras pessoas pelos seus pecados [2] e construa uma ferramenta menos que adequada.

Minha ferramenta favorita para análise

A melhor ferramenta do mundo para o trabalho é a biblioteca Parsec (para parsers decentes recursivos) que vem com a linguagem de programação Haskell. Ele se parece muito com o BNF , ou como uma ferramenta especializada ou linguagem específica de domínio para análise (código de exemplo [3]), mas é na verdade apenas uma biblioteca regular em Haskell, o que significa que ele compila na mesma etapa de construção do seu código Haskell, e você pode escrever código Haskell arbitrário e chamar isso dentro de seu analisador, e você pode misturar e combinar outras bibliotecas no mesmo código . (A incorporação de uma linguagem de análise como esta em uma linguagem diferente de Haskell resulta em muitos problemas sintáticos, a propósito. Eu fiz isso em C # e ela funciona muito bem, mas não é tão bonita e sucinta).

Notas:

1 Richard Stallman diz, em Por que você não deve usar o Tcl

A principal lição do Emacs é que uma linguagem para extensões não deve ser uma mera “linguagem de extensão”. Deve ser uma linguagem de programação real, projetada para escrever e manter programas substanciais. Porque as pessoas vão querer fazer isso!

[2] Sim, estou sempre com cicatrizes de usar essa “linguagem”.

Observe também que quando eu submetai esta input, a pré-visualização estava correta, mas o analisador menos adequado do SO usou meu tag de âncora no primeiro parágrafo , provando que os analisadores não são algo para se brincar, porque se você usar regexes e um off hacks você provavelmente vai ter algo sutil e pequeno errado .

[3] Snippet de um analisador Haskell usando Parsec: uma calculadora de quatro funções estendida com expoentes, parênteses, espaço em branco para multiplicação e constantes (como pi e e).

 aexpr = expr `chainl1` toOp expr = optChainl1 term addop (toScalar 0) term = factor `chainl1` mulop factor = sexpr `chainr1` powop sexpr = parens aexpr < |> scalar < |> ident powop = sym "^" >>= return . (B Pow) < |> sym "^-" >>= return . (\xy -> B Pow x (B Sub (toScalar 0) y)) toOp = sym "->" >>= return . (B To) mulop = sym "*" >>= return . (B Mul) < |> sym "/" >>= return . (B Div) < |> sym "%" >>= return . (B Mod) < |> return . (B Mul) addop = sym "+" >>= return . (B Add) < |> sym "-" >>= return . (B Sub) scalar = number >>= return . toScalar ident = literal >>= return . Lit parens p = do lparen result < - p rparen return result 

O algoritmo do pátio de manobras é a ferramenta certa para isso. A Wikipédia é realmente confusa sobre isso, mas basicamente o algoritmo funciona assim:

Diga, você quer avaliar 1 + 2 * 3 + 4. Intuitivamente, você “sabe” que tem que fazer o 2 * 3 primeiro, mas como você consegue esse resultado? A chave é perceber que quando você está escaneando a string da esquerda para a direita, você irá avaliar um operador quando o operador que o segue tiver uma precedência menor (ou igual a). No contexto do exemplo, aqui está o que você deseja fazer:

  1. Olhe para: 1 + 2, não faça nada.
  2. Agora olhe para 1 + 2 * 3, ainda não faça nada.
  3. Agora olhe para 1 + 2 * 3 + 4, agora você sabe que 2 * 3 tem que ser avaliado porque o próximo operador tem menor precedência.

Como você implementa isso?

Você quer ter duas pilhas, uma para números e outra para operadores. Você empurra números para a pilha o tempo todo. Você compara cada novo operador com aquele no topo da pilha, se o que está no topo da pilha tiver prioridade mais alta, você o tira da pilha do operador, tira os operandos da pilha de números, aplica o operador e empurra o resultado na pilha de números. Agora você repete a comparação com o operador top of stack.

Voltando ao exemplo, funciona assim:

N = [] Ops = []

  • Leia 1. N = [1], Ops = []
  • Ler +. N = [1], Ops = [+]
  • Leia 2. N = [1 2], Ops = [+]
  • Leia * . N = [1 2], Ops = [+ *]
  • Leia 3. N = [1 2 3], Ops = [+ *]
  • Ler +. N = [1 2 3], Ops = [+ *]
    • Pop 3, 2 e executar 2 * 3 e empurrar o resultado para N. N = [1 6], Ops = [+]
    • + é deixado associativo, então você quer pop 1, 6 off também e executar o +. N = [7], Ops = [].
    • Por fim, empurre o [+] para a pilha do operador. N = [7], Ops = [+].
  • Leia 4. N = [7 4]. Ops = [+].
  • Você está sem input, então você quer esvaziar as pilhas agora. Após o qual você obterá o resultado 11.

Lá, isso não é tão difícil, é? E não faz invocações para quaisquer gramáticas ou geradores de parser.

http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

Muito boa explicação de diferentes abordagens:

  • Reconhecimento recursivo-descendente
  • O algoritmo do pátio de manobras
  • A solução clássica
  • Precedência de escalada

Escrito em linguagem simples e pseudo-código.

Eu gosto de ‘precedência subir’ um.

Há um bom artigo aqui sobre a combinação de um analisador de descendência recursiva simples com análise de precedência do operador. Se você recentemente escreveu escritas, deve ser muito interessante e instrutivo ler.

Há muito tempo, criei meu próprio algoritmo de análise, que não consegui encontrar em nenhum livro sobre análise (como o Dragon Book). Olhando os indicadores para o algoritmo do Shunting Yard, vejo a semelhança.

Cerca de 2 anos atrás, eu fiz um post sobre isso, completo com o código-fonte Perl, em http://www.perlmonks.org/?node_id=554516 . É fácil portar para outras linguagens: a primeira implementação que fiz foi no montador Z80.

É ideal para cálculos diretos com números, mas você pode usá-lo para produzir uma tree de análise, se necessário.

Atualização Como mais pessoas podem ler (ou executar) o Javascript, reimplementamos meu analisador em Javascript, depois que o código foi reorganizado. O analisador inteiro tem menos de 5k de código Javascript (cerca de 100 linhas para o analisador, 15 linhas para uma function de invólucro), incluindo relatório de erros e comentários.

Você pode encontrar uma demonstração ao vivo em http://users.telenet.be/bartl/expressionParser/expressionParser.html .

 // operator table var ops = { '+' : {op: '+', precedence: 10, assoc: 'L', exec: function(l,r) { return l+r; } }, '-' : {op: '-', precedence: 10, assoc: 'L', exec: function(l,r) { return lr; } }, '*' : {op: '*', precedence: 20, assoc: 'L', exec: function(l,r) { return l*r; } }, '/' : {op: '/', precedence: 20, assoc: 'L', exec: function(l,r) { return l/r; } }, '**' : {op: '**', precedence: 30, assoc: 'R', exec: function(l,r) { return Math.pow(l,r); } } }; // constants or variables var vars = { e: Math.exp(1), pi: Math.atan2(1,1)*4 }; // input for parsing // var r = { string: '123.45+33*8', offset: 0 }; // r is passed by reference: any change in r.offset is returned to the caller // functions return the parsed/calculated value function parseVal(r) { var startOffset = r.offset; var value; var m; // floating point number // example of parsing ("lexing") without aid of regular expressions value = 0; while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++; if(r.string.substr(r.offset, 1) == ".") { r.offset++; while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++; } if(r.offset > startOffset) { // did that work? // OK, so I'm lazy... return parseFloat(r.string.substr(startOffset, r.offset-startOffset)); } else if(r.string.substr(r.offset, 1) == "+") { // unary plus r.offset++; return parseVal(r); } else if(r.string.substr(r.offset, 1) == "-") { // unary minus r.offset++; return negate(parseVal(r)); } else if(r.string.substr(r.offset, 1) == "(") { // expression in parens r.offset++; // eat "(" value = parseExpr(r); if(r.string.substr(r.offset, 1) == ")") { r.offset++; return value; } r.error = "Parsing error: ')' expected"; throw 'parseError'; } else if(m = /^[a-z_][a-z0-9_]*/i.exec(r.string.substr(r.offset))) { // variable/constant name // sorry for the regular expression, but I'm too lazy to manually build a varname lexer var name = m[0]; // matched string r.offset += name.length; if(name in vars) return vars[name]; // I know that thing! r.error = "Semantic error: unknown variable '" + name + "'"; throw 'unknownVar'; } else { if(r.string.length == r.offset) { r.error = 'Parsing error at end of string: value expected'; throw 'valueMissing'; } else { r.error = "Parsing error: unrecognized value"; throw 'valueNotParsed'; } } } function negate (value) { return -value; } function parseOp(r) { if(r.string.substr(r.offset,2) == '**') { r.offset += 2; return ops['**']; } if("+-*/".indexOf(r.string.substr(r.offset,1)) >= 0) return ops[r.string.substr(r.offset++, 1)]; return null; } function parseExpr(r) { var stack = [{precedence: 0, assoc: 'L'}]; var op; var value = parseVal(r); // first value on the left for(;;){ op = parseOp(r) || {precedence: 0, assoc: 'L'}; while(op.precedence < stack[stack.length-1].precedence || (op.precedence == stack[stack.length-1].precedence && op.assoc == 'L')) { // precedence op is too low, calculate with what we've got on the left, first var tos = stack.pop(); if(!tos.exec) return value; // end reached // do the calculation ("reduce"), producing a new value value = tos.exec(tos.value, value); } // store on stack and continue parsing ("shift") stack.push({op: op.op, precedence: op.precedence, assoc: op.assoc, exec: op.exec, value: value}); value = parseVal(r); // value on the right } } function parse (string) { // wrapper var r = {string: string, offset: 0}; try { var value = parseExpr(r); if(r.offset < r.string.length){ r.error = 'Syntax error: junk found at offset ' + r.offset; throw 'trailingJunk'; } return value; } catch(e) { alert(r.error + ' (' + e + '):\n' + r.string.substr(0, r.offset) + '<*>' + r.string.substr(r.offset)); return; } } 

Ajudaria se você pudesse descrever a gramática que você está usando atualmente para analisar. Parece que o problema pode estar aí!

Editar:

O fato de você não entender a questão gramatical e que “você escreveu isso manualmente” explica muito bem por que você está tendo problemas com as expressões do formulário ‘1 + 11 * 5’ (ou seja, com precedência do operador) . Procurar por ‘gramática para expressões aritméticas’, por exemplo, deve fornecer alguns bons indicadores. Tal gramática não precisa ser complicada:

  ::=  +  |  -  |   ::=  *  |  /  |   ::= x | y | ... | (  ) | -  |  

faria o truque, por exemplo, e pode ser trivialmente aumentado para cuidar de algumas expressões mais complicadas (incluindo funções, por exemplo, ou poderes, …).

Eu sugiro que você dê uma olhada neste segmento, por exemplo.

Quase todas as introduções a gramáticas / parsing tratam expressões aritméticas como um exemplo.

Note que usar uma gramática não implica em usar uma ferramenta específica ( a la Yacc, Bison, …). De fato, você certamente já está usando a seguinte gramática:

  ::  |     :: + | - | * | /  ::  | () 

(ou algo do tipo) sem saber!

Você já pensou em usar o Boost Spirit ? Ele permite que você escreva gramáticas semelhantes a EBNF em C ++ assim:

 group = '(' >> expression >> ')'; factor = integer | group; term = factor >> *(('*' >> factor) | ('/' >> factor)); expression = term >> *(('+' >> term) | ('-' >> term)); 

Como você coloca sua pergunta, não há necessidade de recursion. A resposta é três coisas: notação Postfix mais algoritmo Shunting Yard mais avaliação de expressão Postfix:

1). Notação postfix = inventada para eliminar a necessidade de especificação de precedência explícita. Leia mais na net, mas aqui está a essência: infixo expressão (1 + 2) * 3, enquanto fácil para humanos ler e processar não muito eficiente para computação via máquina. O que é? Regra simples que diz “rewrite a expressão pelo cache em precedência, então sempre processá-la da esquerda para a direita”. Então infix (1 + 2) * 3 se torna um postfix 12 + 3 *. POST porque o operador é colocado sempre APÓS os operandos.

2). Avaliando a expressão postfix. Fácil. Leia números fora da string postfix. Empurre-os em uma pilha até que um operador seja visto. Verifique o tipo de operador – unário? binário? terciário? Pop quantos operandos fora da pilha, conforme necessário para avaliar este operador. Avalie. Empurre o resultado de volta na pilha! E ur quase pronto. Continue fazendo isso até que a pilha tenha apenas uma input = valor que você está procurando.

Vamos fazer (1 + 2) * 3, que está no postfix, é “12 + 3 *”. Leia o primeiro número = 1. Empurre-o na pilha. Leia a seguir. Número = 2. Empurre-o na pilha. Leia a seguir. Operador. Qual? +. Que tipo? Binário = precisa de dois operandos. Pop stack duas vezes = argright é 2 e argleft é 1. 1 + 2 é 3. Empurre 3 de volta na pilha. Leia a seguir da string postfix. É um número. 3.Push Leia a seguir. Operador. Qual? * Que tipo? Binário = precisa de dois números -> pilha pop duas vezes. Primeiro, entre no argright, pela segunda vez no argleft. Avaliar operação – 3 vezes 3 é 9. Empurre 9 na pilha. Leia o próximo postfix char. É nulo. Fim da input. Pop stack onec = essa é sua resposta.

3). Shunting Yard é usado para transformar a expressão infix humana (facilmente) legível em expressão postfix (também humana facilmente legível após alguma prática). Fácil de codificar manualmente. Veja comentários acima e net.

Existe uma linguagem que você deseja usar? O ANTLR permitirá que você faça isso de uma perspectiva Java. Adrian Kuhn tem um ótimo artigo sobre como escrever uma gramática executável em Ruby; Na verdade, seu exemplo é quase exatamente o seu exemplo de expressão aritmética.

Depende de como “geral” você quer que seja.

Se você quer que ele seja realmente genérico, como ser capaz de analisar funções matemáticas, assim como o pecado (4 + 5) * cos (7 ^ 3), você provavelmente precisará de uma tree de análise.

Em que, eu não acho que uma implementação completa é adequada para ser colada aqui. Eu sugiro que você verifique um dos infames ” Dragon book “.

Mas se você quer apenas o suporte à precedência , então você pode fazer isso primeiro convertendo a expressão para a forma postfix na qual um algoritmo que você pode copiar e colar deve estar disponível no google ou eu acho que você pode codificá-lo com um binário tree.

Quando você o tem na forma de postfix, então é um pedaço de bolo a partir de então, já que você já entende como a pilha ajuda.

Eu sugeriria fazer batota e usar o Algoritmo Shunting Yard . É um meio fácil de escrever um analisador simples do tipo calculadora e tem precedência em consideração.

Se você quiser dissecar corretamente as coisas e ter variables, etc. envolvidas, então eu iria em frente e escreveria um parser recursivo de descida como sugerido por outros aqui, no entanto se você simplesmente exigir um analisador no estilo da calculadora então esse algoritmo deve ser suficiente 🙂

Eu encontrei isso na PIClist sobre o algoritmo Shunting Yard :

Harold escreve:

Lembro-me de ler, há muito tempo, um algoritmo que converteu expressões algébricas em RPN para facilitar a avaliação. Cada valor de infixo ou operador ou parênteses foi representado por um vagão de trem em uma pista. Um tipo de carro se dividiu em outra pista e o outro continuou em frente. Não me lembro dos detalhes (obviamente!), Mas sempre achei que seria interessante codificar. Isso está de volta quando eu estava escrevendo 6800 (não 68000) código de assembly.

Este é o “algorythm do pátio de manobras” e é o que a maioria dos analisadores de máquinas usam. Veja o artigo sobre análise na Wikipedia. Uma maneira fácil de codificar o algorythm do pátio de manobras é usar duas pilhas. Uma é a pilha “push” e a outra é a pilha “reduzir” ou “resultado”. Exemplo:

pstack = () // empty rstack = () input: 1 + 2 * 3 precedência = 10 // menor reduzir = 0 // não reduzir

start: token ‘1’: isnumber, colocar em pstack (push) token ‘+’: isoperator set precedence = 2 se precedence

para reduzir, pop elementos da pilha de empurrar e colocá-los na pilha de resultados, sempre trocar os 2 itens principais no pstack se eles estiverem no formato ‘operador’ ‘número’:

pstack: ‘1’ ‘+’ ‘2’ ‘ ‘ ‘3’ rstack: () … pstack: () rstack: ‘3’ ‘2’ ‘ ‘ ‘1’ ‘+’

se a expressão fosse:

1 * 2 + 3

então, o gatilho de redução teria sido a leitura do token ‘+’ que tem precendece mais baixo que o ‘*’ já pressionado, então teria feito:

pstack: ‘1’ ‘ ‘ ‘2’ rstack: () … pstack: () rstack: ‘1’ ‘2’ ‘

e então pressionou ‘+’ e depois ‘3’ e finalmente reduziu:

pstack: ‘+’ ‘3’ rstack: ‘1’ ‘2’ ‘ ‘ … pstack: () rstack: ‘1’ ‘2’ ‘ ‘ ‘3’ ‘+’

Portanto, a versão curta é: push numbers, ao pressionar os operadores para verificar a precedência do operador anterior. Se foi mais alto que o operador que deve ser empurrado agora, primeiro reduza, depois empurre o operador atual. Para lidar com os pais simplesmente salve a precedência do operador ‘anterior’, e coloque uma marca no pstack que diz ao algorythm de redução para parar de reduzir ao resolver o interior de um par paren. O parente de fechamento triggers uma redução assim como o final da input, e também remove a marca de parêntese aberta do pstack e restaura a precedência de ‘operação anterior’ para que a análise possa continuar após o paren de fechamento de onde parou. Isso pode ser feito com recursion ou sem (dica: use uma pilha para armazenar a precedência anterior ao encontrar um ‘(‘ …). A versão generalizada disso é usar um algoritmo de shunting yard implementado pelo gerador de analisador, f.ex. usando yacc ou bison ou taccle (tcl analog of yacc).

Pedro

-Adão

Eu postei fonte para um Java Math Evaluator ultracompacto (1 aula, <10 KiB) no meu site. Este é um analisador descendente recursivo do tipo que causou a explosão craniana para o poster da resposta aceita.

Suporta precedência completa, parênteses, variables ​​nomeadas e funções de argumento único.

Eu liberei um analisador de expressões baseado no algoritmo Shunting Yard de Dijkstra , sob os termos da Licença Apache 2.0 :

http://projects.congrace.de/exp4j/index.html

Outro recurso para análise de precedência é a input do analisador de precedência de operador na Wikipedia. Cobre o algoritmo de shunt do yard de Dijkstra, e um algoritmo alternativo de tree, mas mais notavelmente cobre um algoritmo de substituição de macro realmente simples que pode ser implementado trivialmente em frente a qualquer parser ignorante de precedência:

 #include  int main(int argc, char *argv[]){ printf("(((("); for(int i=1;i!=argc;i++){ if(argv[i] && !argv[i][1]){ switch(argv[i]){ case '^': printf(")^("); continue; case '*': printf("))*(("); continue; case '/': printf("))/(("); continue; case '+': printf(")))+((("); continue; case '-': printf(")))-((("); continue; } } printf("%s", argv[i]); } printf("))))\n"); return 0; } 

Invoque-o como:

 $ cc -o parenthesise parenthesise.c $ ./parenthesise a \* b + c ^ d / e ((((a))*((b)))+(((c)^(d))/((e)))) 

Que é incrível em sua simplicidade e muito compreensível.

Eu implementei um analisador descendente recursivo em Java no projeto MathEclipse Parser . Também pode ser usado como um módulo do Google Web Toolkit

Atualmente estou trabalhando em uma série de artigos que constroem um analisador de expressões regulares como uma ferramenta de aprendizado para padrões de design e programação legível. Você pode dar uma olhada no readablecode . O artigo apresenta um claro uso do algoritmo de shunting yards.

Eu escrevi um analisador de expressões em F # e escrevi sobre isso aqui . Ele usa o algoritmo de shunting yard, mas em vez de converter de infix para RPN, adicionei uma segunda pilha para acumular os resultados dos cálculos. Ele manipula corretamente a precedência do operador, mas não suporta operadores unários. Eu escrevi isso para aprender F #, não para aprender a análise de expressão, no entanto.

Uma solução Python usando pyparsing pode ser encontrada aqui . Analisar a notação de infix com vários operadores com precedência é bastante comum e, portanto, o pyparsing também inclui o construtor de expressão operatorPrecedence. Com ele você pode facilmente definir expressões booleanas usando “AND”, “OR”, “NOT”, por exemplo. Ou você pode expandir sua aritmética de quatro funções para usar outros operadores, como! para fatorial, ou ‘%’ para módulo, ou adicione operadores P e C para calcular combinações e permutações. Você pode escrever um analisador de infixo para notação matricial, que inclui o tratamento de operadores ‘-1’ ou ‘T’ (para inversão e transposição). O exemplo operatorPrecedence de um analisador de 4 funções (com ‘!’ Jogado por diversão) está aqui e um analisador e avaliador mais completo está aqui .

Eu sei que esta é uma resposta tardia, mas eu acabei de escrever um pequeno parser que permite que todos os operadores (prefixo, postfix e infix-left, infix-right e nonassociative) tenham precedência arbitrária.

Vou expandir isso para uma linguagem com suporte a DSL arbitrário, mas eu só queria salientar que não é necessário um analisador customizado para a precedência do operador, pode-se usar um analisador generalizado que não precisa de tabelas, e apenas procura a precedência de cada operador como aparece. As pessoas mencionam parsers personalizados do Pratt ou analisadores de pátio de manobras que podem aceitar inputs ilegais – este não precisa ser personalizado e (a menos que haja um bug) não aceitará input incorreta. Não está completo em um sentido, foi escrito para testar o algoritmo e sua input está em uma forma que precisará de algum pré-processamento, mas há comentários que deixam claro.

Note que alguns tipos comuns de operadores estão faltando, por exemplo, o tipo de operador usado para indexação, isto é, tabela [index] ou chamando uma function function (parâmetro-expressão, …) Eu vou adicioná-los, mas pense em ambos como postfix operadores onde o que vem entre os delímetros ‘[‘ e ‘]’ ou ‘(‘ e ‘)’ é analisado com uma instância diferente do analisador de expressões. Desculpe ter deixado isso de fora, mas a parte do postfix está em – adicionando o resto provavelmente quase o dobro do tamanho do código.

Como o analisador tem apenas 100 linhas de código de raquete, talvez eu deva apenas colá-lo aqui, espero que isso não seja mais do que o stackoverflow permite.

Alguns detalhes sobre decisões arbitrárias:

Se um operador postfix de precedência baixa estiver competindo pelos mesmos blocos infix como um operador de prefixo de baixa precedência, o operador de prefixo vence. Isso não aparece na maioria das linguagens, já que a maioria não tem operadores postfix de baixa precedência. – por exemplo: ((dados a) (esquerda 1 +) (pré 2 não) (dados b) (pós 3!) (esquerda 1 +) (dados c)) é a + não b! + c onde não é um operador de prefixo e! é o operador postfix e ambos têm precedência menor que + então eles querem agrupar de maneiras incompatíveis como (a + não b!) + c ou como a + (não b! + c) nesses casos o operador prefix sempre ganha, então o segundo é a maneira como analisa

Os operadores infixos não-associativos estão realmente lá, de modo que você não precisa fingir que os operadores que retornam tipos diferentes do que eles fazem fazem sentido juntos, mas sem ter tipos diferentes de expressões para cada um, é um kludge. Assim, nesse algoritmo, os operadores não associativos se recusam a se associar não apenas a si mesmos, mas a qualquer operador com a mesma precedência. Esse é um caso comum, pois < <= ==> = etc não se associam na maioria dos idiomas.

A questão de como diferentes tipos de operadores (à esquerda, prefixo, etc) quebram os laços na precedência é um que não deveria aparecer, porque não faz sentido dar aos operadores de diferentes tipos a mesma precedência. Esse algoritmo faz algo nesses casos, mas eu não estou nem me importando em descobrir exatamente o que é porque essa gramática é uma má ideia em primeiro lugar.

 #lang racket ;cool the algorithm fits in 100 lines! (define MIN-PREC -10000) ;format (pre prec name) (left prec name) (right prec name) (nonassoc prec name) (post prec name) (data name) (grouped exp) ;for example "not a*-7+5 < b*b or c >= 4" ;which groups as: not ((((a*(-7))+5) < (b*b)) or (c >= 4))" ;is represented as '((pre 0 not)(data a)(left 4 *)(pre 5 -)(data 7)(left 3 +)(data 5)(nonassoc 2 < )(data b)(left 4 *)(data b)(right 1 or)(data c)(nonassoc 2 >=)(data 4)) ;higher numbers are higher precedence ;"(a+b)*c" is represented as ((grouped (data a)(left 3 +)(data b))(left 4 *)(data c)) (struct prec-parse ([data-stack #:mutable #:auto] [op-stack #:mutable #:auto]) #:auto-value '()) (define (pop-data stacks) (let [(data (car (prec-parse-data-stack stacks)))] (set-prec-parse-data-stack! stacks (cdr (prec-parse-data-stack stacks))) data)) (define (pop-op stacks) (let [(op (car (prec-parse-op-stack stacks)))] (set-prec-parse-op-stack! stacks (cdr (prec-parse-op-stack stacks))) op)) (define (push-data! stacks data) (set-prec-parse-data-stack! stacks (cons data (prec-parse-data-stack stacks)))) (define (push-op! stacks op) (set-prec-parse-op-stack! stacks (cons op (prec-parse-op-stack stacks)))) (define (process-prec min-prec stacks) (let [(op-stack (prec-parse-op-stack stacks))] (cond ((not (null? op-stack)) (let [(op (car op-stack))] (cond ((>= (cadr op) min-prec) (apply-op op stacks) (set-prec-parse-op-stack! stacks (cdr op-stack)) (process-prec min-prec stacks)))))))) (define (process-nonassoc min-prec stacks) (let [(op-stack (prec-parse-op-stack stacks))] (cond ((not (null? op-stack)) (let [(op (car op-stack))] (cond ((> (cadr op) min-prec) (apply-op op stacks) (set-prec-parse-op-stack! stacks (cdr op-stack)) (process-nonassoc min-prec stacks)) ((= (cadr op) min-prec) (error "multiply applied non-associative operator")) )))))) (define (apply-op op stacks) (let [(op-type (car op))] (cond ((eq? op-type 'post) (push-data! stacks `(,op ,(pop-data stacks) ))) (else ;assume infix (let [(tos (pop-data stacks))] (push-data! stacks `(,op ,(pop-data stacks) ,tos))))))) (define (finish input min-prec stacks) (process-prec min-prec stacks) input ) (define (post input min-prec stacks) (if (null? input) (finish input min-prec stacks) (let* [(cur (car input)) (input-type (car cur))] (cond ((eq? input-type 'post) (cond ((< (cadr cur) min-prec) (finish input min-prec stacks)) (else (process-prec (cadr cur)stacks) (push-data! stacks (cons cur (list (pop-data stacks)))) (post (cdr input) min-prec stacks)))) (else (let [(handle-infix (lambda (proc-fn inc) (cond ((< (cadr cur) min-prec) (finish input min-prec stacks)) (else (proc-fn (+ inc (cadr cur)) stacks) (push-op! stacks cur) (start (cdr input) min-prec stacks)))))] (cond ((eq? input-type 'left) (handle-infix process-prec 0)) ((eq? input-type 'right) (handle-infix process-prec 1)) ((eq? input-type 'nonassoc) (handle-infix process-nonassoc 0)) (else error "post op, infix op or end of expression expected here")))))))) ;alters the stacks and returns the input (define (start input min-prec stacks) (if (null? input) (error "expression expected") (let* [(cur (car input)) (input-type (car cur))] (set! input (cdr input)) ;pre could clearly work with new stacks, but could it reuse the current one? (cond ((eq? input-type 'pre) (let [(new-stack (prec-parse))] (set! input (start input (cadr cur) new-stack)) (push-data! stacks (cons cur (list (pop-data new-stack)))) ;we might want to assert here that the cdr of the new stack is null (post input min-prec stacks))) ((eq? input-type 'data) (push-data! stacks cur) (post input min-prec stacks)) ((eq? input-type 'grouped) (let [(new-stack (prec-parse))] (start (cdr cur) MIN-PREC new-stack) (push-data! stacks (pop-data new-stack))) ;we might want to assert here that the cdr of the new stack is null (post input min-prec stacks)) (else (error "bad input")))))) (define (op-parse input) (let [(stacks (prec-parse))] (start input MIN-PREC stacks) (pop-data stacks))) (define (main) (op-parse (read))) (main) 

Here is a simple case recursive solution written in Java. Note it does not handle negative numbers but you can do add that if you want to:

 public class ExpressionParser { public double eval(String exp){ int bracketCounter = 0; int operatorIndex = -1; for(int i=0; i 

}

Algorithm could be easily encoded in C as recursive descent parser.

 #include  #include  /* * expression -> sum * sum -> product | product "+" sum * product -> term | term "*" product * term -> number | expression * number -> [0..9]+ */ typedef struct { int value; const char* context; } expression_t; expression_t expression(int value, const char* context) { return (expression_t) { value, context }; } /* begin: parsers */ expression_t eval_expression(const char* symbols); expression_t eval_number(const char* symbols) { // number -> [0..9]+ double number = 0; while (isdigit(*symbols)) { number = 10 * number + (*symbols - '0'); symbols++; } return expression(number, symbols); } expression_t eval_term(const char* symbols) { // term -> number | expression expression_t number = eval_number(symbols); return number.context != symbols ? number : eval_expression(symbols); } expression_t eval_product(const char* symbols) { // product -> term | term "*" product expression_t term = eval_term(symbols); if (*term.context != '*') return term; expression_t product = eval_product(term.context + 1); return expression(term.value * product.value, product.context); } expression_t eval_sum(const char* symbols) { // sum -> product | product "+" sum expression_t product = eval_product(symbols); if (*product.context != '+') return product; expression_t sum = eval_sum(product.context + 1); return expression(product.value + sum.value, sum.context); } expression_t eval_expression(const char* symbols) { // expression -> sum return eval_sum(symbols); } /* end: parsers */ int main() { const char* expression = "1+11*5"; printf("eval(\"%s\") == %d\n", expression, eval_expression(expression).value); return 0; } 

next libs might be useful: yupana – strictly arithmetic operations; tinyexpr – arithmetic operations + C math functions + one provided by user; mpc – parser combinators

Explicação

Let’s capture sequence of symbols that represent algebraic expression. First one is a number, that is a decimal digit repeated one or more times. We will refer such notation as production rule.

 number -> [0..9]+ 

Addition operator with its operands is another rule. It is either number or any symbols that represents sum "*" sum sequence.

 sum -> number | sum "+" sum 

Try substitute number into sum "+" sum that will be number "+" number which in turn could be expanded into [0..9]+ "+" [0..9]+ that finally could be reduced to 1+8 which is correct addition expression.

Other substitutions will also produce correct expression: sum "+" sum -> number "+" sum -> number "+" sum "+" sum -> number "+" sum "+" number -> number "+" number "+" number -> 12+3+5

Bit by bit we could resemble set of production rules aka grammar that express all possible algebraic expression.

 expression -> sum sum -> difference | difference "+" sum difference -> product | difference "-" product product -> fraction | fraction "*" product fraction -> term | fraction "/" term term -> "(" expression ")" | number number -> digit+ 

To control operator precedence alter position of its production rule against others. Look at grammar above and note that production rule for * is placed below + this will force product evaluate before sum . Implementation just combines pattern recognition with evaluation and thus closely mirrors production rules.

 expression_t eval_product(const char* symbols) { // product -> term | term "*" product expression_t term = eval_term(symbols); if (*term.context != '*') return term; expression_t product = eval_product(term.context + 1); return expression(term.value * product.value, product.context); } 

Here we eval term first and return it if there is no * character after it this is left choise in our production rule otherwise – evaluate symbols after and return term.value * product.value this is right choise in our production rule ie term "*" product