Writing expressions: Infix, Postfix and Prefix

Question

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+(0*A)

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

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.