Expresiones de escritura: Infijo, Postfix y Prefijo.

Question

Mi tarea es escribir una aplicación (desafortunadamente en C) que lea la expresión en notación infija (con variables, operadores unarios y binarios) y almacenarla en la memoria, luego evaluarla. Además, se deben realizar verificaciones de corrección.

por ejemplo:

  

3 * (A + B) - (- 2-78) * 2 + (0 * A)

Después de obtener todos los valores, el programa debería calcularlo.

La pregunta es: ¿Cuál es la mejor manera de hacer esto? (Con optimización y validación)

¿Qué notación elegir como base del árbol?

¿Debo representar la expresión como un árbol? Si es así, puedo optimizarlo fácilmente (simplemente suelte los nodos que devuelven 0 o algo más).

Saludos,

Answer 1

El enlace sugerido en el comentario de Greg Hewgill anterior contiene toda la información que necesitará:

Si insistes en escribir el tuyo,

• un analizador de descenso recursivo es probablemente la forma más sencilla de hacerlo a mano.
• De lo contrario, podrías usar una herramienta como Bison (ya que estás trabajando en C). Este tutorial es el mejor que he visto para trabajar con Flex y Bison (o Lex / Yacc)

También puede buscar " evaluador de expresiones " en Codeproject: tienen muchos artículos sobre el tema.

Me encontré con el evaluador de expresiones del programa M4 hace algún tiempo. Puedes estudiar su código para ver cómo funciona. Creo que este enlace en Google Codesearch es la versión que vi.

Answer 2

Su pregunta apunta a los requisitos que se le asignan a su solución:

  

desafortunadamente en C

por lo que algunas sugerencias aquí podrían no estar permitidas. Sin embargo, sugeriría que este es un problema bastante complicado de resolver, y que sería mucho mejor tratando de encontrar una biblioteca adecuada que pueda vincular a su código C para hacer esto por usted. . Esto probablemente reduciría el tiempo y el esfuerzo necesarios para que el código funcione, y reduciría el esfuerzo de mantenimiento continuo. Por supuesto, tendrías que pensar en la licencia, pero me sorprendería si no hubiera una buena biblioteca de análisis / evaluación " ahí fuera " Lo que podría hacer un buen trabajo de esto.