Expressões de escrita: infix, postfix e prefixo

Question

Minha tarefa é escrever um aplicativo (infelizmente em C) que lê a expressão na notação de infix (com variáveis, operadores unários e binários) e armazená -la na memória e avaliá -la. Além disso, as verificações para correção devem ser executadas.

por exemplo:

3*(a+b)-(-2-78)*2+(0*a)

Depois de obter todos os valores, o programa deve calculá -lo.

A questão é: qual é a melhor maneira de fazer isso? (Com otimização e validação)

Que notação para a escolha como a base da árvore?

Devo representar a expressão como árvore? Nesse caso, posso otimizá -lo facilmente (basta soltar nós que retornam 0 ou smth mais).

Saúde,

Answer 1

O link sugerido no comentário de Greg Hewgill acima contém todas as informações que você precisará:

Se você insistir em escrever o seu próprio,

• uma Analisador de descida recursiva é provavelmente a maneira mais simples de fazê -lo manualmente.
• Caso contrário, você poderá usar uma ferramenta como o bisonte (já que está trabalhando em c). Este tutorial é o melhor que já vi para trabalhar com Flex e Bison (ou Lex/Yacc)

Você também pode procurar por "Avaliador de expressão" No CodeProject - eles têm muitos artigos sobre o assunto.

Me deparei com o avaliador de expressão do programa M4 há algum tempo. Você pode estudar seu código para ver como ele funciona. Eu penso esse link No Google CodEsearch está a versão que vi.

Answer 2

Sua pergunta sugere os requisitos que estão sendo colocados em sua solução:

infelizmente em c

Portanto, algumas sugestões aqui podem não ser permitidas. No entanto, eu sugeriria que esse é um problema bastante complicado de resolver, e que você seria Muito de Melhor tentar encontrar uma biblioteca existente adequada que você possa vincular ao seu código C para fazer isso por você. Isso provavelmente reduziria o tempo e o esforço necessários para que o código funcionasse e reduziria o esforço de manutenção contínuo. Obviamente, você teria que pensar em licenciamento, mas eu ficaria surpreso se não houvesse uma boa biblioteca de análise/avaliação "lá fora", que poderia fazer um bom trabalho nisso.