Analisador de equação (expressão) com precedência?
https://stackoverflow.com/questions/28256
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Desenvolvi um analisador de equações usando um algoritmo de pilha simples que lidará com operadores binários (+, -, |, &, *, /, etc), operadores unários (!) e parênteses.
Usar esse método, no entanto, deixa tudo com a mesma precedência - ele é avaliado da esquerda para a direita, independentemente do operador, embora a precedência possa ser aplicada usando parênteses.
Então, agora, "1+11*5" retorna 60, e não 56, como seria de esperar.
Embora isso seja adequado para o projeto atual, quero ter uma rotina de uso geral que possa usar em projetos posteriores.
Editado para maior clareza:
Qual é um bom algoritmo para analisar equações com precedência?
Estou interessado em algo simples de implementar e entender que posso codificar sozinho para evitar problemas de licenciamento com o código disponível.
Gramática:
Não entendo a questão gramatical - escrevi isso à mão.É simples o suficiente para não ver necessidade de YACC ou Bison.Só preciso calcular strings com equações como "2+3 * (42/13)".
Linguagem:
Estou fazendo isso em C, mas estou interessado em um algoritmo, não em uma solução específica de linguagem.C é de baixo nível o suficiente para ser fácil de converter para outro idioma caso seja necessário.
Exemplo de código
eu postei o código de teste para o analisador de expressão simples Eu estava falando acima.Os requisitos do projeto foram alterados e nunca precisei otimizar o código para desempenho ou espaço, pois não foi incorporado ao projeto.Está na forma detalhada original e deve ser facilmente compreensível.Se eu fizer mais alguma coisa em termos de precedência de operador, provavelmente escolherei o truque macro porque corresponde ao resto do programa em simplicidade.Porém, se algum dia eu usar isso em um projeto real, optarei por um analisador mais compacto/rápido.
Pergunta relacionada
-Adão
Solução
O jeito difícil
Você quer um analisador descendente 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, veja o sinal de mais e inicie uma nova "sessão" de análise recursiva começando com 11...e certifique-se de analisar o 11 * 5 em seu próprio fator, produzindo uma árvore de análise com 1 + (11 * 5).
Tudo isso parece tão doloroso até mesmo 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 criar um termo e, em vez disso, analisar o 11 ele mesmo como um fator.Minha cabeça já está explodindo.É possível com a estratégia decente recursiva, mas existe uma maneira melhor...
A maneira mais fácil (certa)
Se você usa uma ferramenta GPL como o Bison, provavelmente não precisa se preocupar com problemas de licenciamento, já que o código C gerado pelo bison não é coberto pela GPL (IANAL, mas tenho certeza que as ferramentas GPL não forçam a GPL código/binários gerados;por exemplo, a Apple compila código como, digamos, Aperture com GCC e eles o vendem sem precisar GPL desse código).
Baixar Bisão (ou algo equivalente, ANTLR, etc.).
Geralmente há algum código de exemplo no qual você pode simplesmente executar o bison e obter o código C desejado que demonstra esta calculadora de quatro funções:
http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html
Observe o código gerado e veja que 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 algo (especialmente se você ler o livro Dragon e aprender sobre gramática), 2) você evita NIH tentando reinventar a roda.Com uma ferramenta geradora de analisador real, você realmente tem esperança de ampliar mais tarde, mostrando a outras pessoas que você conhece que os analisadores são o domínio das ferramentas de análise.
Atualizar:
As pessoas aqui ofereceram muitos bons conselhos.Meu único aviso contra pular as ferramentas de análise ou apenas usar o algoritmo Shunting Yard ou um analisador recursivo decente feito à mão é que pequenas linguagens de brinquedo1 algum dia pode se transformar em grandes linguagens reais com funções (sin, cos, log) e variáveis, condições e loops for.
Flex/Bison pode muito bem ser um exagero para um intérprete pequeno e simples, mas um analisador + avaliador único pode causar problemas no futuro quando alterações precisam ser feitas ou recursos precisam ser adicionados.Sua situação irá variar e você precisará usar seu julgamento;apenas não punir outras pessoas pelos seus pecados [2] e construir uma ferramenta nada adequada.
Minha ferramenta favorita para análise
A melhor ferramenta do mundo para o trabalho é o Parsec biblioteca (para analisadores recursivos decentes) que vem com a linguagem de programação Haskell.Parece muito BNF, ou como alguma 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 ela é compilada na mesma etapa de construção que o resto do seu código Haskell, e você pode escrever código Haskell arbitrário e chamá-lo em seu analisador, e pode misturar e combinar outras bibliotecas tudo no mesmo código.(A propósito, incorporar uma linguagem de análise como essa em uma linguagem diferente de Haskell resulta em muita confusão sintática.Fiz isso em C# e funciona muito bem, mas não é tão bonito e sucinto.)
Notas:
1 Richard Stallman diz, em Por que você não deve usar Tcl
A principal lição do Emacs é que um idioma para extensões não deve ser uma mera "linguagem de extensão".Ela deve ser uma linguagem de programação real, projetado para escrever e manter programas substanciais.Porque as pessoas vai querer fazer isso!
[2] Sim, estou sempre com medo de usar essa "linguagem".
Observe também que quando enviei esta entrada, a visualização estava correta, mas O analisador menos que adequado do SO comeu minha tag âncora próxima no primeiro parágrafo, provando que analisadores não são algo para se brincar porque se você usar regexes e hacks únicos você provavelmente entenderá algo sutil e pequeno errado.
[3] Trecho de um analisador Haskell usando Parsec:uma calculadora de quatro funções estendida com expoentes, parênteses, espaços 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 . (\x y -> 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
Outras dicas
O algoritmo de pátio de manobra é a ferramenta certa para isso.A Wikipedia é realmente confusa sobre isso, mas basicamente o algoritmo funciona assim:
Digamos que você queira avaliar 1 + 2 * 3 + 4.Intuitivamente, você “sabe” que tem que fazer o 2*3 primeiro, mas como conseguir esse resultado?A chave é perceber que, ao digitalizar a string da esquerda para a direita, você avaliará um operador quando o operador que segue tem uma precedência inferior (ou igual a).No contexto do exemplo, eis o que você deseja fazer:
- Olhe para a:1 + 2, não faça nada.
- Agora olhe para 1 + 2 * 3, ainda não faça nada.
- Agora olhe para 1 + 2 * 3 + 4, agora você sabe que 2 * 3 precisa ser avaliado porque o próximo operador tem precedência menor.
Como você implementa isso?
Você deseja ter duas pilhas, uma para números e outra para operadores.Você coloca números na pilha o tempo todo.Você compara cada novo operador com aquele no topo da pilha, se aquele no topo da pilha tiver prioridade mais alta, você o retira da pilha de operadores, retira os operandos da pilha de números, aplica o operador e envia o resultado na pilha de números.Agora você repete a comparação com o operador do topo da pilha.
Voltando ao exemplo, funciona assim:
N = [ ] Ops = [ ]
- Leia 1.N = [1], Operações = [ ]
- Leia +.N = [1], Operações = [+]
- Leia 2.N = [1 2], Operações = [+]
- Ler
*.N = [1 2], Operações = [+ *] - Leia 3.N = [1 2 3], Operações = [+ *]
- Leia +.N = [1 2 3], Operações = [+ *]
- Pop 3, 2 e execute 2
*3 e empurre o resultado para N.N = [1 6], Operações = [+] +é associativo à esquerda, então você deseja retirar 1, 6 também e executar o +.N = [7], Operações = [].- Por fim, coloque o [+] na pilha do operador.N = [7], Operações = [+].
- Pop 3, 2 e execute 2
- Leia 4.N = [7 4].Operações = [+].
- Você está sem entrada, então deseja esvaziar as pilhas agora.Após o qual você obterá o resultado 11.
Pronto, isso não é tão difícil, não é?E não faz invocações para nenhuma gramática ou gerador de analisador.
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
Muito boa explicação de diferentes abordagens:
- Reconhecimento de descida recursiva
- O algoritmo do pátio de manobras
- A solução clássica
- Escalada de precedência
Escrito em linguagem simples e pseudocódigo.
Eu gosto de 'escalar precedência'.
Há um artigo legal aqui sobre como combinar um analisador descendente recursivo simples com análise de precedência de operador.Se você escreveu analisadores recentemente, sua leitura deve ser muito interessante e instrutiva.
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 para as dicas do algoritmo Shunting Yard, vejo a semelhança.
Cerca de 2 anos atrás, fiz um post sobre isso, completo com código-fonte Perl, em http://www.perlmonks.org/?node_id=554516.É fácil migrar para outros idiomas:a primeira implementação que fiz foi em assembler Z80.
É ideal para cálculos diretos com números, mas você pode usá-lo para produzir uma árvore de análise, se necessário.
Atualizar Como mais pessoas podem ler (ou executar) Javascript, reimplementei meu analisador em Javascript, depois que o código foi reorganizado.Todo o analisador tem menos de 5k de código Javascript (cerca de 100 linhas para o analisador, 15 linhas para uma função wrapper), incluindo relatórios 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 l-r; } },
'*' : {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 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 de 'você ter escrito isso à mão' provavelmente explica por que você está tendo problemas com expressões da forma '1+11*5' (ou seja, com precedência de operador) .Pesquisar no Google por 'gramática para expressões aritméticas', por exemplo, deve render algumas boas dicas.Tal gramática não precisa ser complicada:
<Exp> ::= <Exp> + <Term> |
<Exp> - <Term> |
<Term>
<Term> ::= <Term> * <Factor> |
<Term> / <Factor> |
<Factor>
<Factor> ::= x | y | ... |
( <Exp> ) |
- <Factor> |
<Number>
faria o truque, por exemplo, e pode ser aumentado trivialmente para cuidar de algumas expressões mais complicadas (incluindo funções, por exemplo, ou potências,...).
Eu sugiro que você dê uma olhada esse fio, por exemplo.
Quase todas as introduções à gramática/análise tratam as expressões aritméticas como exemplo.
Observe que usar uma gramática não implica de forma alguma usar uma ferramenta específica (a la Yacc, Bison,...).Na verdade, você certamente já está usando a seguinte gramática:
<Exp> :: <Leaf> | <Exp> <Op> <Leaf>
<Op> :: + | - | * | /
<Leaf> :: <Number> | (<Exp>)
(ou algo do tipo) sem saber!
Você já pensou em usar Impulsionar o Espírito?Ele permite que você escreva gramáticas do tipo EBNF em C++ assim:
group = '(' >> expression >> ')';
factor = integer | group;
term = factor >> *(('*' >> factor) | ('/' >> factor));
expression = term >> *(('+' >> term) | ('-' >> term));
Ao colocar sua pergunta, não há necessidade de qualquer recursão.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 explícita de precedência.Leia mais na net, mas aqui está a essência:expressão infixa ( 1 + 2 ) * 3 embora seja fácil de ser lida e processada por humanos, não é muito eficiente para computação via máquina.O que é?Regra simples que diz "reescrever a expressão armazenando em cache na precedência e sempre processá-la da esquerda para a direita".Portanto, o infixo ( 1 + 2 ) * 3 torna-se um postfix 12+3*.POST porque o operador é colocado sempre APÓS os operandos.
2).Avaliando a expressão postfix.Fácil.Leia os números 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?Retire quantos operandos da pilha forem necessários para avaliar este operador.Avalie.Empurre o resultado de volta para a pilha!E você está quase terminando.Continue fazendo isso até que a pilha tenha apenas uma entrada = valor que você está procurando.
Vamos fazer ( 1 + 2 ) * 3 que está no postfix é "12+3*".Leia o primeiro número = 1.Empurre-o para a pilha.Leia a seguir.Número = 2.Empurre-o para a pilha.Leia a seguir.Operador.Qual deles?+.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.Empurre.Leia a seguir.Operador.Qual deles?*.Que tipo?Binário = precisa de dois números -> empilhar duas vezes.Primeiro entre em argright, segunda vez em argleft.Avalie a operação - 3 vezes 3 é 9. Empurre 9 na pilha.Leia o próximo caractere postfix.É nulo.Fim da entrada.Pop stack onec = essa é a sua resposta.
3).Shunting Yard é usado para transformar expressões infixas (facilmente) legíveis por humanos em expressões pós-fixadas (também facilmente legíveis por humanos após alguma prática).Fácil de codificar manualmente.Veja os comentários acima e na rede.
Depende de quão "geral" você deseja que seja.
Se você quiser que seja realmente geral, como ser capaz de analisar funções matemáticas, bem como sin(4+5)*cos(7^3) você provavelmente precisará de um analisar árvore.
No qual, não creio que seja adequado colar aqui uma implementação completa.Eu sugiro que você dê uma olhada em um dos infames "Livro do dragão".
Mas se você quiser apenas suporte de precedência, então você poderia fazer isso primeiro convertendo a expressão para o formato postfix no qual um algoritmo que você pode copiar e colar deve estar disponível em Google ou acho que você mesmo pode codificá-lo com uma árvore binária.
Quando você o tem no formato postfix, é moleza a partir de então, pois você já entende como a pilha ajuda.
Eu sugeriria trapacear e usar o Algoritmo de pátio de manobras.É um meio fácil de escrever um analisador simples do tipo calculadora e leva em consideração a precedência.
Se você deseja tokenizar as coisas corretamente e ter variáveis, etc.envolvido, então eu iria em frente e escreveria um analisador descendente recursivo como sugerido por outros aqui, no entanto, se você simplesmente precisar de um analisador estilo calculadora, então este algoritmo deve ser suficiente :-)
Encontrei isso no PIClist sobre o Algoritmo de pátio de manobras:
Haroldo escreve:
Lembro-me de ter lido, há muito tempo, um algoritmo que convertia expressões algébricas para RPN para fácil avaliação.Cada valor infixo ou operador ou parêntese era representado por um vagão ferroviário em um pista.Um tipo de carro se partiu para outra pista e o outro continuou em linha reta adiante.Não me lembro dos detalhes (obviamente!), mas sempre pensei seria interessante codificar.Isto é quando eu estava escrevendo 6800 (não 68000) código de montagem.
Este é o "algoritmo do pátio de manobra" e é o que a maioria dos analisadores de máquinas usar.Veja o artigo sobre análise em Wikipédia.Uma maneira fácil de codificar o Shunting yard algorythm é usar dois Pilhas.Um deles é a pilha "push" e o outro o "reduzir" ou "resultar" pilha.Exemplo:
pstack = () // rstack vazio = () entrada:1+2*3 precedência = 10 // menor reduzir = 0 // não reduzir
começar:símbolo '1':isnumber, colocar em pstack (push) token '+':isoperador definir precedência=2 se a precedência < previous_operator_precedence então reduce() // veja abaixo colocar '+' em pstack (push) token '2':isnúmero, colocar no token pstack (push) '*':isoperator, definir precedência=1, colocar em pstack (push) // verificar precedência como acima do token '3':isnumber, colocar em pstack (push) fim da entrada, precisa reduce (meta é pstack vazio) reduce() terminado
para reduzir, elementos pop do empurrão empilhar e colocá-los no resultado pilha, sempre troque os 2 principais itens em pstack se eles são da forma «Operador» «número»:
pilha:'1' '+' '2' '' '3' pilha:() ...pilha:() pilha:'3' '2' '' '1' '+'
se a expressão fosse:
1*2+3
então o gatilho de redução teria foi a leitura do token '+' que tem precedência menor que o '*' já empurrou, então teria terminado:
pilha:'1' '' '2' pilha:() ...pilha:() pilha:'1' '2' ''
e, em seguida, empurrou '+' e depois '3' e em seguida, finalmente, reduziu:
pilha:'+' '3' pilha:'1' '2' '' ...pilha:() pilha:'1' '2' '' '3' '+'
Portanto, a versão curta é:números de empurrar, ao empurrar os operadores verifique o precedência do operador anterior.Se foi maior que a da operadora Isso deve ser empurrado agora, primeiro reduzir e, em seguida, empurrar a corrente operador.Para lidar com parens basta salvar a precedência do "anterior" operador, e colocar uma marca no pstack que diz ao algarismo redutor para pare de reduzir ao resolver o interior de um par paren.O paren de fechamento desencadeia uma redução, assim como o fim de entrada, e também remove o aberto marca paren do pstack, e restaura a 'operação anterior' precedência para que a análise possa continuar após o paren fechado de onde saiu desligado.Isso pode ser feito com recursão ou sem (dica:usar uma pilha para armazenar a precedência anterior quando encontrando um '('...).O versão generalizada deste é para usar um gerador de analisador implementado Pátio de manobra Algorythm, F.Ex.Usando YACC ou bisão ou taccle (TCL análogo de YACC).
Peter
-Adão
Publiquei a fonte de um ultracompacto (1 classe, <10 KiB) Avaliador de matemática Java no meu site.Este é um analisador descendente recursivo do tipo que causou a explosão craniana do autor da resposta aceita.
Suporta precedência total, parênteses, variáveis nomeadas e funções de argumento único.
eu lancei um analisador de expressão baseado em Pátio de manobras de Dijkstra algoritmo, nos termos do Licença Apache 2.0:
Outro recurso para análise de precedência é o Analisador de precedência de operador entrada na Wikipédia.Abrange o algoritmo de pátio de manobras de Dijkstra e um algoritmo alternativo de árvore, mas cobre mais notavelmente um algoritmo de substituição de macro realmente simples que pode ser implementado trivialmente na frente de qualquer analisador ignorante de precedência:
#include <stdio.h>
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))))
O que é incrível em sua simplicidade e muito compreensível.
Eu implementei um analisador descendente recursivo em Java no Analisador MathEclipse projeto.Também poderia ser usado como Kit de ferramentas da Web do Google módulo
Atualmente estou trabalhando em uma série de artigos sobre a construção de um analisador de expressões regulares como uma ferramenta de aprendizagem para padrões de design e programação legível.Você pode dar uma olhada código legível.O artigo apresenta um uso claro do algoritmo de pátios de manobra.
Eu escrevi um analisador de expressão em F# e blogei sobre isso aqui.Ele usa o algoritmo do pátio de manobras, mas em vez de converter de infixo para RPN, adicionei uma segunda pilha para acumular os resultados dos cálculos.Ele lida corretamente com a precedência do operador, mas não oferece suporte a operadores unários.Escrevi isso para aprender F#, mas não para aprender análise de expressões.
Uma solução Python usando pyparsing pode ser encontrada aqui.A análise da notação infixa com vários operadores com precedência é bastante comum e, portanto, a análise py também inclui o infixNotation (anteriormente operatorPrecedence) construtor de expressão.Com ele você pode definir facilmente 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 permutações e combinações.Você poderia escrever um analisador infixo para notação de matriz, que inclui o tratamento de operadores '-1' ou 'T' (para inversão e transposição).O exemplo de operatorPrecedence de um analisador de 4 funções (com '!' inserido por diversão) é aqui e um analisador e avaliador com mais recursos é aqui.
Eu sei que esta é uma resposta tardia, mas acabei de escrever um pequeno analisador que permite que todos os operadores (prefixo, postfix e infixo à esquerda, infixo à direita e não associativo) tenham precedência arbitrária.
Vou expandir isso para uma linguagem com suporte DSL arbitrário, mas só queria salientar que não são necessários analisadores personalizados para precedência de operador, é possível usar um analisador generalizado que não precisa de tabelas, e apenas procura a precedência de cada operador conforme aparece.As pessoas têm mencionado analisadores Pratt personalizados ou analisadores de manobras que podem aceitar entradas ilegais - este não precisa ser personalizado e (a menos que haja um bug) não aceita entradas incorretas.De certa forma, não está completo, foi escrito para testar o algoritmo e sua entrada está em um formato que precisará de algum pré-processamento, mas há comentários que deixam isso claro.
Observe que alguns tipos comuns de operadores estão faltando, por exemplo, o tipo de operador usado para indexar ou seja, tabela[índice] ou chamar uma função (expressão de parâmetro, ...) Vou adicioná-los, mas pense em ambos como operadores de pós-fixação, onde o que vem entre os delímetros '[' e ']' ou '(' e ')' é analisado com uma instância diferente do analisador de expressão.Desculpe ter deixado isso de fora, mas a parte do postfix está incluída - adicionar o restante provavelmente quase dobrará o 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 não seja mais longo do que o stackoverflow permite.
Alguns detalhes sobre decisões arbitrárias:
Se um operador postfix de baixa precedência estiver competindo pelos mesmos blocos infixos que um operador de prefixo de baixa precedência, o operador de prefixo vence.Isso não aparece na maioria dos idiomas, pois a maioria não possui operadores postfix de baixa precedência.- por exemplo:((dados a) (esquerda 1 +) (pré 2 não)(dados b)(post 3 !) (esquerda 1 +) (dados c)) é a+not b!+c onde not é um operador de prefixo e !é operador de pós-fixo e ambos têm menor precedência do que + para que eles queiram agrupar de maneiras incompatíveis como (a+não b!) +c ou como a+(não b!+c) Nesses casos, o operador de prefixo sempre vence, então o segundo é a maneira como ele analisa
Os operadores infixos não associativos estão realmente lá, para que você não precise fingir que os operadores que retornam tipos diferentes fazem sentido juntos, mas sem ter tipos de expressão diferentes para cada um, é um erro.Como tal, neste algoritmo, os operadores não associativos recusam-se a associar-se não apenas a si próprios, 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 (esquerdo, prefixo, etc.) rompem os laços de precedência não deveria ser levantada, porque realmente não faz sentido dar a operadores de tipos diferentes a mesma precedência.Esse algoritmo faz alguma coisa nesses casos, mas nem estou me preocupando em descobrir exatamente o quê, 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)
Aqui está uma solução recursiva de caso simples escrita em Java.Observe que ele não lida com números negativos, mas você pode adicionar isso se quiser:
public class ExpressionParser {
public double eval(String exp){
int bracketCounter = 0;
int operatorIndex = -1;
for(int i=0; i<exp.length(); i++){
char c = exp.charAt(i);
if(c == '(') bracketCounter++;
else if(c == ')') bracketCounter--;
else if((c == '+' || c == '-') && bracketCounter == 0){
operatorIndex = i;
break;
}
else if((c == '*' || c == '/') && bracketCounter == 0 && operatorIndex < 0){
operatorIndex = i;
}
}
if(operatorIndex < 0){
exp = exp.trim();
if(exp.charAt(0) == '(' && exp.charAt(exp.length()-1) == ')')
return eval(exp.substring(1, exp.length()-1));
else
return Double.parseDouble(exp);
}
else{
switch(exp.charAt(operatorIndex)){
case '+':
return eval(exp.substring(0, operatorIndex)) + eval(exp.substring(operatorIndex+1));
case '-':
return eval(exp.substring(0, operatorIndex)) - eval(exp.substring(operatorIndex+1));
case '*':
return eval(exp.substring(0, operatorIndex)) * eval(exp.substring(operatorIndex+1));
case '/':
return eval(exp.substring(0, operatorIndex)) / eval(exp.substring(operatorIndex+1));
}
}
return 0;
}
}
O algoritmo pode ser facilmente codificado em C como analisador descendente recursivo.
#include <stdio.h>
#include <ctype.h>
/*
* 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;
}
as próximas bibliotecas podem ser úteis: Yupana - operações estritamente aritméticas; tinyexpr - operações aritméticas + funções matemáticas C + uma fornecida pelo usuário; mpc - combinadores de analisador
Explicação
Vamos capturar a sequência de símbolos que representam a expressão algébrica.O primeiro é um número, ou seja, um dígito decimal repetido uma ou mais vezes.Chamaremos essa notação de regra de produção.
number -> [0..9]+
Operador de adição com seus operandos é outra regra.Ou é number ou quaisquer símbolos que representem sum "*" sum seqüência.
sum -> number | sum "+" sum
Tente substituir number em sum "+" sum isso será number "+" number que por sua vez poderia ser expandido para [0..9]+ "+" [0..9]+ que finalmente poderia ser reduzido a 1+8 que é a expressão de adição correta.
Outras substituições também produzirão expressão correta: sum "+" sum -> number "+" sum -> number "+" sum "+" sum -> number "+" sum "+" number -> number "+" number "+" number -> 12+3+5
Pouco a pouco poderíamos nos assemelhar a um conjunto de regras de produção também conhecido como gramática que expressam todas as expressões algébricas possíveis.
expression -> sum
sum -> difference | difference "+" sum
difference -> product | difference "-" product
product -> fraction | fraction "*" product
fraction -> term | fraction "/" term
term -> "(" expression ")" | number
number -> digit+
Para controlar a precedência do operador, altere a posição de sua regra de produção em relação a outras.Observe a gramática acima e observe que a regra de produção para * é colocado abaixo + isso vai forçar product avaliar antes sum.A implementação apenas combina o reconhecimento de padrões com a avaliação e, portanto, reflete de perto as regras de produção.
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);
}
Aqui nós avaliamos term primeiro e devolva-o se não houver * personagem depois dele esta é a escolha deixada em nossa regra de produção caso contrário - avalia os símbolos depois e retorna term.value * product.value esta é a escolha certa em nossa regra de produção, ou seja, term "*" product
