I would once again like to stress that you should spend a fair amount of effort sketching out the algorithms and trying them on paper before diving into the implementation and wrestling with C. As with the previous programming assignment, I expect the bulk of the frustration and challenge not to be with the concepts and ideas behind the data structures, but in wrestling with the details -- memory management, dealing with strings, converting between data types, etc.

This program does not lend itself to as straightforward an implementation path as the previous one did. In part, this is because all the pieces are tightly interrelated (for example, it's hard to test that you've correctly read an expression into a binary tree without already having the ability to print out binary expression trees, unless you use the debugger). In part, it's also because the final implementation can (and should) be done with a small number of tight, elegant recursive functions which are almost as hard to break into smaller pieces as they are to write correctly in the first place.

I give my best attempt to break the program into a number of small steps below. Note, however, that the direct path from no code to the final solution is probably more direct than the step-by-step path I give below. However, if you're not confident in your coding, and don't mind taking a small step off the direct path from time to time, it's still a very reasonable approach to take.

  1. Spend some time reading the program description and making sure that you understand it on paper before you start implementing anything. Make sure to also spend some time thinking about the ADTs that you will use. What will you store in your binary tree nodes? What operations will your binary tree support? What will you store in your hash table and what interface will you use?

  2. Set up the header file for your binary tree ADT. You won't need to supply the implementation right away, but you will probably want the definitions when setting up the hash table.

  3. Spend some time setting up your hash table implementation. Note that Weiss provides hash table implementations for separate chaining and quadratic probing. You may also implement a hash table from scratch or use one from another source if you prefer, as long as you use it in a way that's consistent with our discussion in class. Note that Weiss provides lots of the hard bits -- an implementation of separate chaining and/or quadratic probing as well as a reasonable hash function for strings. However, you'll almost definitely have to rework things a bit in order to hash a string value and associate a binary tree with it (probably using one of the two main strategies we discussed in class).

  4. Write some code that just does some sample stores and finds to the hash table to make sure that it's working as you'd expect.

  5. Write some code that classifies a string/character array as an operator, a variable name, or a numeric constant. You will undoubtedly use this somewhere in your program, but where you use it will probably depend on how you store your expression tree.

  6. Write your main interpreter loop so that it reads the command being requested (the first character) and ignores the rest of the statement for the time being. You might make it print out the command being requested, to make sure that this is working (plus you'll eventually be able to replace the print statements with an appropriate function call). Make it so that the interpreter quits when the quit command is requested.

  7. Make your program handle variable definitions by storing the variable into the hash table without its definition. Make the print and evaluate statements simply print the variable name if it has been defined or an appropriate error message if it has not been.

  8. Write a recursive function to read in a prefix expression and create a binary tree for it. Write another recusive function so that you can print this tree back out and make sure it's correct. Run some short tests on these functions to make sure they work as you expect.

  9. Combine the previous two steps so that when a variable is defined, its definition is read in and stored in a binary tree. If you've set up your hash table correctly, you should trivially be able to store the binary tree. It should also be trivial at this point to make printing a variable work by looking it up in the hash table and printing the binary tree associated with it.

  10. Make sure that your hash table is set up so that when a variable is redefined, its old expression tree is replaced with the new one (and preferably, the old tree's memory is released).

  11. Write two routines: one to evaluate a binary expression tree and the second to evaluate a variable by looking it up in the hash table and evaluating its binary expression tree. The first function should be an elegant, recursive function and can be written in one fell swoop if you're careful. Think carefully about what the base cases are and what the recursive cases are.

  12. Hook the routines from the previous step into your interpreter so that evaluation statements result in the given variable being evaluated. A good testing strategy for these routines would be to try cases of the following types in this order: 1) trees that are single numeric values, 2) trees that are expressions of numeric values, 3) trees that are single variable values, 4) trees that are expressions of numeric values mixed with variable values.

  13. Hey look, you're done already! That's six fewer steps than the last assignment! :)