Hier sind einige fragenbasierte Titel, die zum Inhalt Ihres Artikels passen: Einfach und direkt: * Wie man mathematische Ausdrücke in C analysiert: Shunting-Yard-Algorithmus und formale Grammatiken * Analysematte

Mathematische Ausdrücke in C analysieren

Frage:

Wie können Sie bei einer gegebenen mathematischen Ausdruckszeichenfolge einen Analysebaum erstellen? um den Ausdruck darzustellen?

Lösung:

1. Shunting-Yard-Algorithmus:

Der Shunting-Yard-Algorithmus ist ein zweistufiger Ansatz, der einen Infix-Ausdruck in ein Postfix (umgekehrte polnische Notation) umwandelt und dann den Analysebaum erstellt.

• Infix zu Postfix:

  • Erstellen Sie zwei Stapel: Operatorstapel und Ausgabestapel.
  • Scannen Sie den Infixausdruck von links nach rechts.
  • Wenn ein Operand angetroffen wird, schieben Sie ihn auf den Ausgabestapel.
  • Wenn eine linke Klammer angetroffen wird, schieben Sie ihn auf den Operatorstapel.
  • Wenn eine rechte Klammer angetroffen wird Wenn ein Operator angetroffen wird, entfernen Sie die Operatoren aus dem Operatorstapel und schieben Sie sie auf den Ausgabestapel, bis eine linke Klammer gefunden wird.
  • Wenn ein Operator angetroffen wird, schieben Sie ihn auf den Operatorstapel, wenn seine Priorität höher ist als die des obersten Operators Andernfalls werden Operatoren mit höherer Priorität aus dem Operatorstapel entfernt und auf den Ausgabestapel verschoben.

• Postfix zum Analysebaum:

  • Erstellen Sie einen Wurzelknoten für den Analysebaum.
  • Entnehmen Sie Operanden aus dem Ausgabestapel und erstellen Sie Blattknoten für sie.
  • Entnehmen Sie Operatoren aus dem Ausgabestapel und erstellen Sie interne Knoten mit untergeordneten Knoten, die auf die für die Operanden erstellten Knoten verweisen.
  • Hängen Sie die untergeordneten Knoten an den Wurzelknoten an.

2. Formale Grammatik:

Alternativ können Sie eine formale Grammatik für mathematische Ausdrücke definieren und ein Parsing-Tool verwenden, um einen Parser zu generieren. Eine typische Parsing-Expression Grammar (PEG) für mathematische Ausdrücke sieht so aus:

Expr:   Term '+' Expr | Term '-' Expr | Term;
Term:   Factor '*' Term | Factor '/' Term | Factor;
Factor: Number | '(' Expr ')';

Mehrere C/C-Bibliotheken unterstützen PEG-Parsing, wie zum Beispiel:

• boost::spirit
• pyPEG2
• PCRE

Das obige ist der detaillierte Inhalt vonHier sind einige fragenbasierte Titel, die zum Inhalt Ihres Artikels passen: Einfach und direkt: * Wie man mathematische Ausdrücke in C analysiert: Shunting-Yard-Algorithmus und formale Grammatiken * Analysematte. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!