I'm a sophomore in high school and the same thing happened to me over the course of the year, even though I had an excellent CS teacher. Having learned all about binary trees, and all the other AP datastructures, I wrote an algebraic expression parser that builds an expression tree while maintaining operator precedence rules, and evaluates the expression. It correctly informs the user of malformed expressions, etc... Once this much worked, I took the project a step further and added variables stored in a hash table. My goal was basically to make a TI-89 emulater on the computer, and the project turned out to be quite challenging and interesting overall. You might try suggesting a similar project to your students near the end of the school year after the necessary data structures have been covered.
Slashdot Mirror
I'm a sophomore in high school and the same thing happened to me over the course of the year, even though I had an excellent CS teacher. Having learned all about binary trees, and all the other AP datastructures, I wrote an algebraic expression parser that builds an expression tree while maintaining operator precedence rules, and evaluates the expression. It correctly informs the user of malformed expressions, etc... Once this much worked, I took the project a step further and added variables stored in a hash table. My goal was basically to make a TI-89 emulater on the computer, and the project turned out to be quite challenging and interesting overall. You might try suggesting a similar project to your students near the end of the school year after the necessary data structures have been covered.