Wie erstellt man einen abstrakten Baum anstelle eines Postfix-Ausdrucks mit dem Shunting Yard-Algorithmus?

Question

ich es geschaffen, den folgenden Pseudo-Code auf Wikipedia zu finden, die einen Postfix-Ausdruck erstellen zeigt, wie den Rangierbahnhof Algorithmus verwenden:

While there are tokens to be read: 
    Read a token. 
    If the token is a number, then push it to the output queue. 
    If the token is a function token, then push it onto the stack. 
    If the token is a function argument separator (e.g., a comma): 
    Until the token at the top of the stack is a left parenthesis, pop    operators off the stack onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched. 
    If the token is an operator, o1, then: 
     while there is an operator token o2, at the top of the operator stack and either 
    o1 is left-associative and its precedence is less than or equal to that of o2, or 
    o1 is right associative, and has precedence less than that of o2, 
      pop o2 off the operator stack, onto the output queue; 
    at the end of iteration push o1 onto the operator stack. 
If the token is a left parenthesis (i.e. "("), then push it onto the stack. 
If the token is a right parenthesis (i.e. ")"): 
    Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue. 
Pop the left parenthesis from the stack, but not onto the output queue. 
If the token at the top of the stack is a function token, pop it onto the output queue. 
If the stack runs out without finding a left parenthesis, then there are mismatched parentheses. 
When there are no more tokens to read: 
    While there are still operator tokens in the stack: 
     If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses. 
     Pop the operator onto the output queue. 
Exit. 

wie ich diesen Algorithmus ändern Sie einen abstrakten Syntaxbaum zu erzeugen, was sollte ich tun, anstatt Operatoren oder Operanden zu einer Ausgabe zu drücken?

Answer 1

Ich möchte den einfachsten Weg beschreiben, AST mit Rangierbahnhofsalgorithmus zu bauen, aber nicht der effizienteste. Die Idee ist nur, eine Postfix-Zeichenfolge mit diesem Algorithmus zu erstellen und dann AST aus der Postfix-Zeichenfolge zu erstellen, was extrem einfach ist. Expression, zum Beispiel: a * (b + c) + d

Postfix-String für sie:

a b c + * d + 

des Tokens von Postfix String eins nach dem anderen lesen lassen. Wenn das Token eine Variable ist, schieben Sie es auf einen Stapel mit Knoten. Wenn es ein Operand ist, lassen Sie uns zwei höchste Elemente aus dem Stack mit Knoten füllen, erstellen Sie einen anderen Knoten mit dem aktuellen Operanden darin und machen Sie zwei extrahierte Knoten zu untergeordneten Knoten. Drücken Sie dann den neuen Knoten im Knotenstapel.

Am Ende haben wir nur noch einen Knoten im Knotenstapel - die Wurzel des Baumes. Der Baum ist gebaut.

Dieser Algorithmus erfordert zweimal das Lesen der Zeichenfolge, was ein offensichtlicher Nachteil ist. Auf der anderen Seite ist es sehr einfach.

Effizienter Algorithmus, ohne einen Postfix-String zu erstellen, aber mit dem Aufbau eines AST sofort mit Shunty-Yard-Algorithmus wird hier beschrieben: but it's in C++.