Umwandlung in die Postfix Notation in JavaScript

In JavaScript sähe die Umwandlung in die Postfix Notation wie folgt aus:

// der zu berechnende Term, Klammerung der Punktrechnungen erforderlich
var eingabe = '(2*3)+(4*5)'; 

// Ergebnisspeicher für die Postfix Notation der Eingabe
var postfix = new Array();

// Pufferspeicher für die Operatoren während der Umwandlung
var operatorstack = new Array();

// Fehler im Eingabestring
var fehlerfrei = true;

// Hauptschleife, die so lange ausgeführt wird, bis der Eingabestring leer ist
while (fehlerfrei && eingabe.length) {

    // 1. Prüfung: Ist das erste Zeichen eine Klammer '('
    if (eingabe.match(/^\(/)) {
        // Falls ja, dann ignorieren, bzw. aus dem Eingabestring entfernen
        eingabe = eingabe.substring(1);

    // ansonsten: 2. Prüfung: Handelt es sich zu Beginn des Eingabestrings um eine (ganze) Zahl
    } else if (zahl = eingabe.match(/^[0-9]+/)) {
        // Falls ja, die Zahl in den Ausgabespeicher schreiben
        postfix.push(parseInt(zahl[0]));
        // und aus dem Eingabestring entfernen
        eingabe = eingabe.substring(zahl.length);

    // ansonsten: 3. Prüfung: Handelt es sich zu Beginn des Eingabestrings um einen Operator
    } else if (operator = eingabe.match(/^[\+\-\*\:]/)) {

        // Falls ja, den Operator auf den Operatorstapel legen
        operatorstack.push(operator[0]);
        // und aus dem Eingabestring entfernen
        eingabe = eingabe.substring(1);

    // ansonsten: 4. Prüfung: Handelt es sich zu Beginn des Eingabestrings um eine Klammer ')'
    } else if (eingabe.match(/^\)/)) {

        // Falls ja, dann den obersten Operator aus dem Operatorstapel holen und in den Ausgabespeicher schreiben
        postfix.push(operatorstack.pop());
        // und die Klammer aus dem Eingabestring entfernen
        eingabe = eingabe.substring(1);
        
    // ansonsten wurde ein Zeichen gefunden, mit dem nichts angefangen werden kann: Fehler!
    } else {
   
        // gesonderte Abbruchbedingung der Hauptschleife setzen
        fehlerfrei = false;
    }
}

// Nach Abarbeitung des Eingabestrings ggf. noch verbliebene Operatoren in den Ausgabespeicher verschieben.
while (operatorstack.length) {
    postfix.push(operatorstack.pop());
}

Nach Ausführung dieses Programmteils ist der Eingabestring in ein Feld (Array) umgewandelt worden, bei dem der Term in Postfix Notation vorliegt.

Erläuterungen zum Programmcode

• Zeilen 14 und 53:  JavaScript interpretiert den Wert 0 als “falsch” (false). Daher kommen die Schleifenbedingungen ohne Vergleichsoperator aus. Alternativ hätte man hier auch “eingabe.length > 0” schreiben können.
• Zeilen 17, 22, 29 und 37: In diesen Zeilen findet ein Vergleich des Eingabestrings “eingabe” mit einem sogenannten regulären Ausdruck statt. Der reguläre Ausdruck ist zwischen zwei “/” Zeichen vermerkt. Eine detaillierte Erläuterung der regulären Ausdrücke ginge hier zu weit, daher nur die wichtigsten Elemente:
  • ^ am Anfang des regulären Ausdrucks bedeutet, dass hier der zu prüfende String beginnen muss. Der Suchausdruck darf also nicht irgendwo im Text auftauchen, sondern muss am Anfang stehen.
  • [0-9] steht für eine beliebige Ziffer
  • + bedeutet, dass das vorausgehende Element einmal oder mehrfach gefunden werden muss. [0-9]+ steht also für eine beliebige Ziffernfolge
  • Klammern und Rechenoperatoren wie *, +, – und / haben im regulären Ausdruck eine eigene Bedeutung. Möchte man das Zeichen jedoch selber suchen lassen, muss es durch einen Backslash “” maskiert werden.
• Zeilen 24 und 32: Das Ergebnis der Suche (match), so die Suche erfolgreich war, steht in einem Array. Von Bedeutung ist allerdings nur das erste Ergebnis (mehr sollten auch nicht auftreten), so dass auf das erste Element des Ergebnis Arrays zahl[0], bzw. operator[0] zugegriffen wird.

Hinweis: Dieser vereinfachte Code berücksichtigt nur ganze Zahlen, die vier Grundrechenarten und erfordert eine Klammerung der Punktrechnung.

Vorteil dieser Methode: Die Umwandlung in die Polnische Notation führt zugleich zu einer Prüfung des Eingabestrings, so dass Schadcode weitgehend ausgeschlossen werden kann.