Writing Expressions: Infix, Postfix, and Prefix
My task is to write an application (unfortunately in C) that reads an expression in infix notation (with variables, unary and binary operators) and stores it in memory and then evaluates. In addition, validation checks must be performed.
eg:
3 * (A + B) - (- 2-78) * 2 + (0 * A)
After I got all the values, the program should calculate it.
Question: What is the best way to do this? (With optimization and validation)
What designations for selection as the base of the tree?
Should I represent the expression as a tree? If so, I can easily optimize it (just remove the nodes that return 0 or smth else).
Greetings,
source to share
The link suggested in Greg Hewgill's comment above has all the information you need to know:
If you insist on writing your own,
- a recursive descent parser is perhaps the easiest way to do it manually.
- Otherwise, you can use a tool like Bison (since you are working in C). This tutorial is the best I've seen for working with Flex and Bison (or Lex / Yacc)
You can also find the "expression evaluator" on Codeproject - they have many articles on this topic.
I stumbled upon the expression evaluator of an M4 program a while ago. You can examine its code to see how it works. I think this link on Google Codesearch is the version I saw.
source to share
Your question hints at the requirements for your solution:
unsuccessful in C
therefore, some suggestions here may not be valid. However, I would suggest that this is a rather difficult problem to solve, and that you would be much better off trying to find a suitable existing library that you could link with your C code to do it for you. This is likely to reduce the time and effort required to get the code running and reduce ongoing maintenance. Of course, you have to think about licensing, but I would be surprised if there was not a good analysis / evaluation library "out there" that could handle this well.
source to share