Writing expressions: Infix, Postfix and Prefix

Question

Greetings,

My task is to write an app(unfortunatly on C) which reads expression in infix notation(with variables, unary and binary operators) and store it in memory, then evaluate it. Also, checks for correctness should be performed.

for example:

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

After I got all values, program should calculate it.

The question is: What is the best way to do this?(with optimization and validation)

What notation to choice as the base of tree?

Should I represent expression as tree? If so I can easily optimize it(just drop nodes which returns 0 or smth else).

Cheers,

Answer 1

Your question hints at requirements being put on your solution:

unfortunatly on C

so some suggestions here might not be permissible. Nevertheless, I would suggest that this is quite a complicated problem to solve, and that you would be much better off trying to find a suitable existing library which you could link into your C code to do this for you. This would likely reduce the time and effort required to get the code working, and reduce the ongoing maintenance effort. Of course, you'd have to think about licensing, but I'd be surprised if there wasn't a good parsing/evaluation library "out there" which could do a good job of this.

Answer 2

The link suggested in the comment by Greg Hewgill above contains all the info you'll need:

If you insist on writing your own,

• a recursive descent parser is probably the simplest way to do it by hand.
• Otherwise you could use a tool like Bison (since you're working in C). This tutorial is the best I've seen for working with Flex and Bison (or Lex/Yacc)

You can also search for "expression evaluator" on Codeproject - they have a lot of articles on the topic.

I came across the M4 program's expression evaluator some time ago. You can study its code to see how it works. I think this link on Google Codesearch is the version I saw.