Here's how I would do this: 1. Make a binary tree. Leaf nodes stand for your variables (A, B, f, g...). Interior nodes stand for an operation on the values of the interior node's two sons. 2. Go through your statement and put all tokens into a list of leaf nodes. (The operations will eventually be transferred to interior nodes.) 3. Find the range of nodes where the parentheses are most deeply nested. 4. If you have the pattern [left parenthesis] [variable] [right parenthesis], delete the two parentheses nodes. (The variable could also be an interior node.) 5. In this deeply-nested region, replace the pattern [variable] [high-precedence-operation] [variable] with an interior node for the operation, with the two variables as sons. (The variables could also be other interior nodes.) 6. Repeat Step 5 for the low-precedence operations. You should now be able to apply Step 4 on the remaining interior node left in the parentheses. 7. To evaluate the expression, do a post-order traversal on the binary tree, getting the variable values for leaf nodes, and applying the operation to the two values for interior nodes. The result of the evaluation will be left in your root node. I find this approach simpler than the recursive algorithms.
modified on Friday, March 27, 2009 10:10 AM