Expression Evaluation in C++

Question

Hi, I'm writing some excel-like C++ console app for homework. My app should be able to accept formulas for it's cells, for example it should evaluate something like this:

Sum(tablename\fieldname[recordnumber], fieldname[recordnumber], ...)

tablename\fieldname[recordnumber] points to a cell in another table, 
fieldname[recordnumber] points to a cell in current table

or

Sin(fieldname[recordnumber])

or

anotherfieldname[recordnumber]

or

"10" // (simply a number)

something like that. functions are Sum, Ave, Sin, Cos, Tan, Cot, Mul, Div, Pow, Log (10), Ln, Mod

It's pathetic, I know, but it's my homework :'(

So does anyone know a trick to evaluate something like this?

Answer 1

I guess you cannot use yacc/lex (or the like) so you have to parse "manually":
Iterate over the string and divide it into its parts. What a part is depends on you grammar (syntax). That way you can find the function names and the parameters. The difficulty of this depends on the complexity of your syntax.

Maybe you should read a bit about lexical analysis.

Answer 2

Ok, nice homework question by the way.

It really depends on how heavy you want this to be. You can create a full expression parser (which is fun but also time consuming).

In order to do that, you need to describe the full grammar and write a frontend (have a look at lex and yacc or flexx and bison.

But as I see your question you can limit yourself to three subcases:

• a simple value
• a lookup (possibly to an other table)
• a function which inputs are lookups

I think a little OO design can helps you out here.

I'm not sure if you have to deal with real time refresh and circular dependency checks. Else they can be tricky too.

Answer 3

You should write a parser. Parser should take the expression i.e., each line and should identify the command and construct the parse tree. This is the first phase. In the second phase you can evaluate the tree by substituting the data for each elements of the command.

Answer 4

For the parsing, I'd look at Recursive descent parsing. Then have a table that maps all possible function names to function pointers:

struct FunctionTableEntry {
    string name;
    double (*f)(double);
};

Answer 5

Previous responders have hit it on the head: you need to parse the cell contents, and interpret them.

StackOverflow already has a whole slew of questions on building compilers and interperters where you can find pointers to resources. Some of them are:

• http://stackoverflow.com/questions/1669/learning-to-write-a-compiler (#1669 people!)
• http://stackoverflow.com/questions/41785/learning-resources-on-parsers-interpreters-and-compilers
• http://stackoverflow.com/questions/153330/what-are-good-resources-on-compilation
• http://stackoverflow.com/questions/294852/references-needed-for-implementing-an-interpreter-in-c-c
• ...

and so on.

Aside: I never have the energy to link them all together, or even try to build a comprehensive list.