Usually a better way to parse expressions of this type is to use only 1 recursive call per operator level/precedence. Normally you handle all operators (not just 1) of the same level in a single parsing function, while accumulating the result of this level in the return variable. In practice this means that your function ParseExpression should look something like this:
Expression ParseExpression() { Term tLeft = ParseTerm(); while (NextToken().Type == Plus) { tLeft = new Addition(tLeft, ParseTerm()); } return tLeft;}
Notice that three things have changed:
1. The if-statement was replaced with a while-statement,
2. The call to Addition now uses ParseTerm as the second parameter, instead of ParseExpression (the function ParseExpression is now only called once per operator level, and the next level [ParseTerm] is invoked directly rather than through a recursive ParseExpression call),
3. The result is now accumulated in tLeft, which is returned from the function when there are no more operators of this level in the input string.
If you do all your arithmetics like this you get left-associativity for free, while also reducing recursion depth and making the code more understandable. Btw, the grammar this is parsing is: Expression = Term {"+" Term}.
P.S. I am not a C programmer so the code snippet I posted above might contain errors!
[Edited by - Devilogic on September 28, 2006 6:36:57 AM]