Die Umgekehrte Polnische Notation

Verschiedene Notationen  

Nie verzeihen werde ich dem Staat, daß die Umgekehrte Polnische Notation, UPN (auf Englisch RPN für Reverse Polish Notation), nicht zum Pflichtprogramm Mathe gehört. Warum? Weil sie praktischer ist als die "normale" Notation.

Bei der Polnischen Notation sowie der Umgekehrten Polnischen Notation handelt es sich um zwei Schreibweisen für mathematische Gleichungen. Die in der Schule gelernte Schreibweise nennt sich auch Infix-Notation, da hier die Operatoren zwischen den Operanden stehen, wie z.B. in x = 3 + 4 . Dementsprechend nennt sich die von Lukasiewicz erdachte Polnische Notation auch Präfix-Notation, denn hier stehen die Operatoren vor den dazugehörigen Operanden; obige Gleichung würde als als x = + 3 4 geschrieben werden. Diese Notation hat sich nie so richtig durchgesetzt, wohl aber ihr "Bruder", die Postfix-Notation: hier hieße die Gleichung x = 3 4 + . Ein großer Unterschied ist hier eigentlich nicht.

Der größte Nachteil der Präfix- und Postfix-Notation ist der, daß man nicht gut erkennen kann, wo eine Zahl aufhört und die nächste anfängt. Daher werden sie eben nicht häufig verwendet (Das stimmt nicht ganz: vor allem in Polen war die Polnische Notation lange Zeit weit verbreitet. Um so verwunderlicher ist es, daß sie heute ganz aus den Lehrplänen verbannt wurde). Allerdings ändert sich das Ganze, wenn man z.B. Zellen verwendet und jedes Element der Gleichung in eine Zelle schreibt. Und hier kommt ein großer Vorteil von UPN ins Spiel: es ist für Computer viel einfacher zu interpretieren als "unsere" Notation. Dazu wollen wir gleich kommen.

Keine Klammern oder Prioritäten  

Einer der Gründe, warum UPN so einfach für Computer zu verstehen ist, ist die Postfix-Struktur ansich, wie später gezeigt wird. Ein anderer ist der, daß es in UPN keine Klammern gibt. Wie das funktioniert, zeigt folgendes Beispiel.

Nehmen wir folgende Gleichung in Infix-Notation an: x = (3 + 4) • 5

In UPN würde diese Gleichung folgendermaßen lauten: x = 3 4 + 5 •

Da bei UPN die Operationen strikt von links nach rechts ausgeführt werden, würde hier zuerst die Summe errechnet werden, danach das Produkt. Prioritäten von Operatoren spielen dabei keine Rolle. Wenn man die 5 voranstellen würde, also x = 5 • (3 + 4), würde sich folgende Formel ergeben: x = 5 3 4 + •. Das zeigt eine weitere Eigenschaft von UPN: Operatoren beziehen sich immer auf die zwei Terme direkt davor und ersetzen sie durch einen einzigen. In diesem Fall würden also zuerst 3 und 4 addiert werden und das Ergebnis als Term eingesetzt werden.

Dies läßt sich gut durch eine Tabelle veranschaulichen. Nehmen wir als Beispiel folgende Gleichung an:

x = 3 ÷ 4 • (9 + 3) + 3 - (1 - 4), in UPN entspräche das
x = 3 4 ÷ 9 3 + • 3 + 1 4 - -

Diese Gleichung wollen wir nun in einer Tabelle lösen:

Tabelle 1 : Lösung einer UPN-Gleichung

Das Einmaleins der Stacks  

Um mit UPN effektiv arbeiten zu können, muß man sogenannte Stacks (zu Deutsch „Stapel“) kennen. Ein Stack funktioniert eigentlich ganz einfach:

Im Kaufhaus steht ein Stapel voller Konservendosen. Der Stapel kann jederzeit aufgefüllt werden, indem neue Dosen draufgestellt werden. Wenn ein Kunde eine Dose kaufen will, nimmt er sie ebenfalls von ganz oben. Würde er versuchen, sich eine Dose aus der Mitte zu nehmen – na, dann würde der ganze Stapel zusammenstürzen. Und damit kennen wir auch schon das erste und einzige Gesetz der Stacks: Elemente können nur ganz oben abgelegt und auch nur ganz oben entfernt werden (Anmerkung: Wir reden hier von sogenannten FiLo-Stacks. FiLo steht für First in, Last out. Es gibt auch das Gegenteil, nämlich FiFo-Stacks. Hier gilt die Regel First in, First out, was bedeutet, daß man immer nur das Element entfernen kann, was als erstes hineingepackt wurde. Ein Reallife-Äquivalent wäre zum Beispiel ein Kaugummiautomat, der von oben befüllt wird, der Inhalt kommt aber unten wieder hervor). Wenn man an das x-te Element des Stacks will, muß man vorher erst alle x - 1 Elemente darüber herunternehmen. Ansonsten verhält sich ein Stack im Wesentlichen wie ein Array, das heißt er speichert Elemente. Dabei gibt es wie bei Arrays sowohl die statische Variante mit einer festgelegten Anzahl von Elementen, sowie die dynamische Variante, die eben immer genau so groß ist, wie man sie braucht.

Einen Stack per VB zu programmieren ist ebenfalls ganz einfach. Folgende Klasse stellt einen Stack zum Speichern von Strings dar. Die Klasse basiert aus Gründen der Geschwindigkeit auf Arrays, man könnte ihn aber ebenfalls auf doppelt verknüpften Listen basieren lassen. Die Klasse braucht nur drei Methoden: eine, die Elemente hinzufügt (Push()), eine zum Entfernen von Elementen (Pop()), sowie eine Methode zum Auslesen des obersten Elements (Peek()). Außerdem gibt es eine Eigenschaft, die die Zahl der Elemente speichert (Count).

Option Explicit

Private Const CLASSNAME As String = "CStringStack"

Private m_Stack()       As String
Private m_lOffset       As Long
'----------------------------------------------------

Private Sub Class_Initialize()
    Call Clear
End Sub
'----------------------------------------------------

Public Sub Clear()
    m_lOffset = 0
    Erase m_Stack
    ' Speicher reservieren
    ReDim m_Stack(1000) As String
End Sub

Public Sub Push(Item As String)
    If m_lOffset > UBound(m_Stack) Then _
        ReDim Preserve m_Stack(m_lOffset + 1000) As String
    
    m_Stack(m_lOffset) = Item
    m_lOffset = m_lOffset + 1
End Sub

Public Function Pop() As String
    If CBool(m_lOffset) Then
        m_lOffset = m_lOffset - 1
        Pop = m_Stack(m_lOffset)
    Else
        Call Err.Raise( _
            vbObjectError, _
            CLASSNAME, _
            "Cannot pop from empty stack." _
        )
    End If
End Function

Public Property Get Peek() As String
    If CBool(m_lOffset) Then _
        Peek = m_Stack(m_lOffset - 1) _
    Else _
        Call Err.Raise( _
            vbObjectError, _
            CLASSNAME, _
            "Cannot peek from empty stack." _
        )
End Property

Public Property Get Count() As Long
    Count = m_lOffset
End Property

Listing 1: CStringStack.cls

UPN lösen mit Stacks  

Zum Auflösen einer Gleichung in UPN benötigt man einen numerischen Stack. Der Algorithmus zum Lösen ist ganz einfach: Wenn man die Gleichung zum Beispiel in einem Array abgelegt hat (was durchaus sinnvoll ist), kann man durch folgendes Vorgehen die Gleichung lösen:

1. nimm nächstes Element der Gleichungen

2.1. wenn das Element eine Zahl ist, packe sie auf den numerischen Stack
2.2. wenn es sich um einen Operatoren handelt, wende ihn auf die obersten beiden Elemente des Stacks an.

3. wenn alle Elemente durchgegangen worden sind, Pop'e das Ergebnis vom numerischen Stack.

Das ist alles. Mit diesem Rezept können wir bereits einen vollständigen Funktionsparser für UPN schreiben, der die vier Grundrechenarten beherrscht. Er besteht aus einer einzigen Funktion (sowie der Klasse CDoubleStack, die ein numerisches Äquivalent zur obigen Klasse darstellt):

Public Function ParseRPN(Equation As String) As Double
    Dim Tokens()    As String
    Dim NumStack    As CDoubleStack
    Dim I           As Long
    Dim tmpNumber   As Double
    
    Tokens = Split(Equation, " ")
    Set NumStack = New CDoubleStack
    
    For I = 0 To UBound(Tokens)
        If IsNumeric(Tokens(I)) Then
            ' es handelt sich um eine Zahl
            Call NumStack.Push(Val(Tokens(I)))
        Else
            ' es handelt sich um einen Operator
            tmpNumber = NumStack.Pop()
            
            Select Case Tokens(I)
                Case "+"
                    Call NumStack.Push( _
                        NumStack.Pop() + tmpNumber _
                    )
                Case "-"
                    Call NumStack.Push( _
                        NumStack.Pop() - tmpNumber _
                    )
                Case "*"
                    Call NumStack.Push( _
                        NumStack.Pop() * tmpNumber _
                    )
                Case "/"
                    Call NumStack.Push( _
                        NumStack.Pop() / tmpNumber _
                    )
            End Select
        End If
    Next I
    
    ParseRPN = NumStack.Pop()
End Function

Listing 2: UPN-Parser

Diese Funktion erwartet als Eingabe einen String, in dem alle Elemente der RPN-Funktion durch Leerzeichen getrennt sind. Der Rückgabewert ist das Ergebnis. Natürlich ist ein solcher Parser recht eingeschränkt, da keinerlei Fehlerbehandlung stattfindet und außerdem nur vier Rechenarten zur Verfügung stehen. Trotzdem handelt es sich hierbei um einen vollständigen Parser. Seine Einfachheit beweist den enormen Vorteil, den UPN gegenüber der Infix-Notation hat!

Ihre Meinung  

Falls Sie Fragen zu diesem Tutorial haben oder Ihre Erfahrung mit anderen Nutzern austauschen möchten, dann teilen Sie uns diese bitte in einem der unten vorhandenen Themen oder über einen neuen Beitrag mit. Hierzu können sie einfach einen Beitrag in einem zum Thema passenden Forum anlegen, welcher automatisch mit dieser Seite verknüpft wird.