Schrittweise Abarbeitung von Baumstruktur

[Serethos]

Ich habe eine einfache Baumstruktur, bei der jeder Knoten n Kinder haben kann und auf diese verweist. Es ist ein Syntaxbaum zur Darstellung eines mathematischen Ausdrucks (ähnlich S-Expression in Lisp) mit ein paar einfachen Operatoren, wie +, -, * usw. sowie Zahlenwerte.

z.B.: (+ (- 20 10) 50)

Die Struktur auszuwerten ist sehr einfach, indem ich von jedem Knoten rekursiv die evaluate()-Funktion für jedes seiner Kinder aufrufe und das Ergebnis an den Elter zurückgebe.
Nun das Problem. Ich muß die Abarbeitung schrittweise vornehmen können, also anstatt (pseudocode):

int result = root.evaluate();

muß etwas sein wie:

while(...)
{
  int resultOfNode = tree.evaluateNext();
}

Ich habe eine halbfertige Lösung, indem ich den Stack einer Rekursion nachbilde,
alle Knoten nacheinander auf ihn ablege und sobald einer evaluiert werden kann dies tue. Dazu gibt es zwei Stacks, einen für die Funktionen, einen für die Zahlenwerte:

1. solange Knoten zum evaluieren wiederhole:
2. nächster Knoten == Funktion? 
3. ja: pack Knoten auf FunktionsStack
4. nein: pack Knoten auf WerteStack
5. Kann Knoten evaluiert werden?
6. ja: nimm (entferne) n-Argumente von WerteStack, nimm Funktion von Funktionsstack, evaluiere und pack Ergebnis zurück auf 
7. nein: zurück zu 2.

Hier ist aber der kritische Punkt in Zeile 5.: Wie erkenne ich, dass ein Knoten evaluiert werden kann? Erst dachte ich, es würde reichen zu sagen
Wenn so viele Werte auf dem WerteStack liegen, wie die letzt abgelegte Funktion auf dem Funktionsstack Argumente hat, dann evaluiere sie. Das ist aber leider falsch.
Hat jemand einen Vorschlag?