Berechnung von Termen in Polnischer Notation

Liegt der zu berechnende Term nun einmal in polnischer Notation (Postfix Schreibweise) vor, ist die Berechnung denkbar einfach. Von links nach rechts werden die Elemente abgearbeitet.

// Hilfs- und Ergebnisstapel
var stack = new Array();

// Hauptschleife, die so lange ausgeführt wird, wie Elemente im Postfix Array vorhanden sind
while (postfix.length) {
    // erstes Element des Postfix Stapels ziehen und je nach Fall auswerten
    switch (element = postfix.shift()) {
        case ':':
            // Division
            b = stack.pop();
            stack.push(stack.pop() / b);
            break;
        case '*':
            // Multiplikation
            stack.push(stack.pop() * stack.pop());
            break;
        case '+':
            // Addition
            stack.push(stack.pop() + stack.pop());
            break;
        case '-':
            // Subtraktion
            b = stack.pop();
            stack.push(stack.pop() - b);
            break;
        default:
            // Annahme, dass es sich nun nur noch um eine Zahl handeln kann
            stack.push(element);
    }
}

// Das Ergebnis der Berechnung liegt nun oben auf dem Hilfsstapel
var ergebnis = stack.pop();

Dieser extrem überschaubare (und damit billig zu produzierende) Code ist auch der Grund, warum viele preiswerte Taschenrechner Punkt-vor-Strichrechnung nicht beherrschen. In dieser Form hat der Taschenrechner allerdings auch noch Probleme mit negativen Zahlen. oder kann er nicht sauber berechnen.

Erläuterungen zum Programmcode

• Zeilen 10 und 23: push() legt ein Element oben auf einen Stapel. Die Funktion pop() nimmt entsprechend das oberste Element vom Stapel und entfernt es aus dem Array. Da bei der Abarbeitung des Terms von links nach rechts vorgegangen wird, landet der rechte Operator entsprechend auch oben auf dem Stapel, der linke direkt darunter. Während die Reihenfolge der Zahlen bei Multiplikationen und Additionen unkritisch ist, ist diese bei der Subtraktion und Division entscheidend (, bzw. ). Aus diesem Grund müssen die Werte in Variablen zwischengespeichert werden um sie in die richtige Reihenfolge zu bringen.
• Zeile 28: Es wird davon ausgegangen, dass durch die Erstellung des Postfix Arrays bereits ungültige Werte abgefangen wurden. Daher wird hier auf eine gesonderte Prüfung verzichtet und alles, was nicht einer der vier Operatoren ist, als Zahl verstanden.

Nach der allgemeinen Theorie und Fingerübung bringe ich dem Taschenrechner im nächsten Beitrag nun auf einfache Weise noch die Rechenregeln und das Verständnis von negativen sowie reellen Zahlen bei.