Mittwoch, 28. Januar 2009

 

Algorithmus zum Umwandeln einer Infix- in eine Postfix-Notation

Folgender Algorithmus beschreibt die Umwandlung von Infix- in Postfix-Notation (für UPN).






















Zeichen aus Eingabe

Aktion

'('

push('(')

')'

Solange Stapel nicht leer:
 zeichen = pop()
 Wenn zeichen nicht '(':
   schreibe zeichen in die Ausgabe
Verlasse Schleife wenn zeichen '(' ist

neuer Operator (Variable neuerOp)

Wenn Stapel leer:
 push(neuerOp)
sonst:
 Solange Stapel nicht leer ist:
   zeichen = pop()
   Wenn zeichen '(' ist:
      lege zeichen wieder auf den Stapel (push(zeichen))
   Wenn zeichen ein Operator opTop ist und
      wenn opTop < neuerOp:
      push(opTop)
   Wenn opTop >= neuerOp:
      schreibe opTop in die Ausgabe
 Verlasse die Schleife, wenn opTop < neuerOp oder
   wenn das zeichen '(' ist
 push(neuerOp)

EOF (keine weiteren Zeichen)

Solange Stapel nicht leer ist:
 zeichen = pop()
 schreibe zeichen in die Ausgabe


Die Vergleiche opTop >= neuerOp bzw. opTop < neuerOp bedeuten einen Vergleich der Priorität (Auswertungsreihenfolge, Präzendent, Vorrang, Priorität). Es gilt Präzedenz:

  1. (
  2. + und -
  3. * und /
  4. alles Andere (z.B. sin, cos usw.)

Labels: , ,


# Eingestellt von Harald R. Haberstroh @ 11:58
Kommentare:

Kommentar veröffentlichen

Abonnieren Kommentare zum Post [Atom]





<< Startseite

This page is powered by Blogger. Isn't yours?

Abonnieren Posts [Atom]