I am having some trouble making an iterator that can traverse the following type of data structure.

I have a class called Expression, which has one data member, a List<object>.

This list can have any number of children, and some of those children might be other Expression objects.

I want to traverse this structure, and print out every non-list object (but I do want to print out the elements of the list of course), but before entering a list, I want to return "begin nest" and after I just exited a list, I want to return "end nest".

I was able to do this if I ignored the class wherever possible, and just had List<object> objects with List<object> items if I wanted a subExpression, but I would rather do away with this, and instead have an Expressions as the sublists (it would make it easier to do operations on the object. I am aware that I could use extension methods on the List<object> but it would not be appropriate (who wants an Evaluate method on their list that takes no arguments?).

The code that I used to generate the origonal iterator (that works) is:

    public IEnumerator GetEnumerator(){
        return theIterator(expr).GetEnumerator();
    }
    private IEnumerable theIterator(object root) {
        if ((root is List<object>)){
            yield return " begin nest ";
            foreach (var item in (List<object>)root){
                foreach (var item2 in theIterator(item)){
                    yield return item2;
                }
            }
            yield return " end nest ";
        }
        else
            yield return root;
    }

A type swap of List<object> for expression did not work, and lead to a stackOverflow error. How should the iterator be implemented?

Update: Here is the swapped code:

    public IEnumerator GetEnumerator() {
        return this.GetEnumerator();
    }
    private IEnumerable theIterator(object root) {
        if ((root is Expression)) {
            yield return " begin nest ";
            foreach (var item in (Expression)root) {
                foreach (var item2 in theIterator(item))
                    yield return item2;
            }
            yield return " end nest ";
        }
        else
            yield return root;
    }