Wie man einen algebraischen Ausdruck analysiert

Question

Ich werde ein Programm machen, das einen algebraischen Ausdruck analysieren kann.
Zum Beispiel:
<?php echo cal ('5*5+2*2'); ?>
Mein Programm wird wissen, dass es 5 mit 5 multipliziert und 2 mit 2 zuerst, dann plus sie. Ich möchte es selbst analysieren, nicht per php.

Answer 1

Sie können den 'infix'-Ausdruck verwenden und einen Stapel verwenden, um ihn in einen' Präfix 'oder' Postfix'-Ausdruck umzuwandeln, um die Reihenfolge der Operation zu bestimmen (Klammerung, Potenzierung, Multiplikation oder Division, Addition oder Subtraktion).

Zum Beispiel würde der Ausdruck ([5] [*] [5] [+] [2] [*] [2]) in die Postfix-Expression transformiert [5] [5] [*] [2] [2] [*] [+]. Dieser 'Postfix'-Ausdruck kann nun als' fünf und fünf multipliziert, zwei und zwei multipliziert und dann addiert 'interpretiert werden, wodurch die Reihenfolge der Operationen erhalten bleibt.

Eine andere Möglichkeit, an die 'Präfix/Postfix'-Idee zu denken, ist die von mehreren Stapeln. Wenn du auf die Nummer 5 stößt, drücke sie auf den primären Stapel. Wenn Sie auf das Multiplikationssymbol stoßen, speichern Sie es im Sekundärstapel. Wenn du zu den nächsten 5 kommst, drücke sie auf den primären Stapel, dann platziere alle Gegenstände von deinem sekundären Stapel und schiebe sie auf deinen primären Stapel.

Sobald Sie die Operatoren und Operanden in der richtigen Reihenfolge haben, müssen Sie die Elemente vom Stapel entfernen und sie dann auswerten.

Ich erinnere mich, herauszufinden, dieses Problem in meinem Computer Science 102 Kurs in der Schule. Machst du das aus Spaß oder versuchst du es herauszufinden?

Answer 2

Ich würde vorschlagen, dass Sie auf recursive descent parsers schauen, aber anscheinend haben sich die Dinge bewegt, seit ich das letzte Mal in den mittleren 1980er Jahren getan habe. Es scheint, dass ein Parsing Expression Grammar der Weg ist, jetzt zu gehen, wenn Sie die Theorie dahinter verstehen wollen.

Wenn Sie sich nicht weniger über die Theorie kümmern könnte, das ist in Ordnung: die Theorie der Umsetzung bedeutet, dass Sie gehen einen rekursiven Abstieg Parser sowieso am Ende zu schreiben, so können Sie genau das tun :-)