Thinkin'

I sat down and played with the parenthesization problem this afternoon, and I think I have a pretty good handle on it. I wrote a few lines of pseudo-code and I think this scheme will work. Problem I have now is how to translate it into real code. What I am working with (so far) is an array of small structures. Each element (structure) in the array has some fields for things like the:

• number
• operator
• number of open parentheses
• number of close parentheses
• pointer to the next element in the array

If you are paying attention, you will realize you don't really need a pointer to the next element, you're working with an array, for-Pete's-sake (that's an old expression in case you're a whipper-snapper and don't recognize it. In case you wondering, if you don't recognize it, it means you're a whipper-snapper). If you have an array, you don't need pointers, you have an index and you can adjust it to access any element in the array. If you've got pointers in here it means you've gone in and mucked with array and now just using a straight index isn't going to work anymore. And in fact, that is just what happened. I had this nice array and it worked well. Each pointer was initialized to the next element in the array. Because this array describes an expression, when you start evaluating the expression, some of these elements get consumed and so that element is no longer needed. To eliminate these from future consideration, I simply adjusted the pointer of the previous element to point the next element, skipping this one and effectively deleting it from the record.

Now if you interrupt this process, like run the concatenation operation before you run the parenthesizing operation, you are dealing with this semi-corrupt array. With an intact array, I could use a start index and take care of business, but with a corrupt array, I need besides the start index and count, I also need a pointer and a way to tell if the pointer is any good. 

There are several ways to handle this. I could use real pointers instead of my hybrid index-pointers. I could belly up to the bar and do the work necessary to keep track of all these pieces. Or I could compress the array and eliminate the dead elements. I kind of like that one. It promises to be the clearest to write and therefor read. And make working. I hope.