Πράξεις και τελεστές πράξεων και RPN

Η πράξη έχει στα μαθηματικά έναν αυστηρό ορισμό, που εδώ θα προσπαθήσω να τον πω απλά και περιγραφικά.

Έχουμε ένα σύνολο R με πραγματικούς αριθμούς.
Παίρνουμε πρώτα έναν αριθμό α από το σύνολο R.
Παίρνουμε ακόμη έναν αριθμό β από το σύνολο R.
Οι δυό αριθμοί κρατάνε τη σειρά τους, (πρώτα ο α και μετά ο β), κρατάνε την διάταξή τους, είναι ένα διατεταγμένο ζεύγος (α, β).
Η πράξη που θέλουμε να κάνουμε στο ζευγάρι αριθμών (α, β) συμβολίζεται με ένα τελεστή, ας πούμε Τ, και δίνει ένα αποτέλεσμα γ.
[Πιθανή γραφή : γ = ( α Τ β ) ]

Αν είναι αριθμητική πράξη ([πρόσθεση, αφαίρεση, πολλαπλασιασμός, διαίρεση, ύψωση σε δύναμη] όταν δηλαδή ο τελεστής είναι [+, -, *, /, ^]) τότε το γ είναι αριθμός που ανήκει επίσης στο σύνολο R. (Υπάρχουν κι άλλες πράξεις, όπως η ακέραια διαίρεση (με τελεστή \, όπου [7 \ 3] δίνει πηλίκο 2 και υπόλοιπο 1), που διαφέρει από την κανονική διαίρεση ([7 / 3] δίνει πηλίκο 2.3333..., ή μικτό 2 1/3). Για την ακέραια διαίρεση έχουμε ορίσει συναρτήσεις, όπως είναι η DIV και η MOD).

Αν είναι συγκριτική πράξη ([μεγαλύτερο από, μεγαλύτερο ή ίσο, ίσο, μικρότερο ή ίσο, μικρότερο, διάφορο από] όταν δηλαδή ο τελεστής είναι [>, >=, =, <=, <, <>]) τότε το γ είναι μία από τις δύο λογικές τιμές : Αληθής ή Ψευδής. (Υπάρχουν ακόμα οι λογικές πράξεις, (ο τελεστής είναι ΚΑΙ, Ή, ΌΧΙ), που γίνονται σε μεταβλητές (ή εκφράσεις) που έχουν λογικές τιμές, και πάλι το αποτέλεσμα είναι μία από τις δύο λογικές τιμές : Αληθής ή Ψευδής).

Υπάρχουν τρεις τρόποι να γράψουμε τον τελεστή της πράξης και το ζευγάρι (α, β).
(Τ α β), συμβολισμός prefix, ο τελεστής μπροστά. (Προτάθηκε το 1920 από τον Πολωνό μαθηματικό Jan Lukasiewicz).
(α Τ β), συμβολισμός infix, ο τελεστής ανάμεσα.
(α β Τ), συμβολισμός postfix, ο τελεστής ακολουθεί. (Προτάθηκε το 1960 από τους F. L. Bauer και E. W. Dijkstra).

Ο μόνος γνωστός τρόπος για τους μαθητές είναι με τον τελεστή ανάμεσα από τα (α, β).
Για να μην υπάρχουν παρεξηγήσεις, με ποιά σειρά θα γίνουν οι πράξεις, δίνουμε στους τελεστές ιεραρχία εκτέλεσης. Επίσης, χρησιμοποιούμε παρενθέσεις.

Προηγείται η ύψωση σε δύναμη (α^β).
Δεύτερες πράξεις σε ιεραρχία είναι ο πολλαπλασιασμός (α*β) και η διαίρεση (α/β).
Ακολουθούν τρίτες σε ιεραρχία η πρόσθεση (α+β) και η αφαίρεση (α-β).
Αν σε μία έκφραση υπάρχουν παρενθέσεις, βρίσκεται πρώτα η τιμή της έκφρασης της πιο εσωτερικής παρένθεσης.
Αν σε μία έκφραση υπάρχουν πράξεις ίσης ιεραρχίας, εκτελούνται από αριστερά προς τα δεξιά.
Οι συγκριτικοί τελεστές έχουν μικρότερη ιεραρχία.
Οι λογικοί τελεστές έχουν μικρότερη από όλους, αλλά μεταξύ τους (αν θυμάμαι καλά!) προηγείται ο ΌΧΙ, μετά ο ΚΑΙ, μετά ο Ή. Το σωστό είναι να βάζουμε παρενθέσεις, για να μην υπάρχει αμφιβολία.

Ας δούμε ένα παράδειγμα εκτέλεσης πράξεων (Συμβολίζουμε τα ενδιάμεσα αποτελέσματα (results) με R1, R2, κλπ) :
(α - β * (γ + δ * ε)) - ζ / η
(α - β * (γ + R1)) - ζ / η
(α - β * (R2)) - ζ / η
(α - R3) - ζ / η
(R4) - ζ / η
R4 - R5
R6

Μια ενδιαφέρουσα παρατήρηση είναι ότι ο συμβολισμός του Πολωνού (Polish notation) Lukasiewicz και ο συμβολισμός με τον τελεστή να ακολουθεί (ανάστροφος συμβολισμός του Πολωνού, Reverse Polish Notation, RPN) δεν χρειάζονται παρενθέσεις!

Και μπορεί να γραφτεί εύκολα ένα πρόγραμμα που να βρίσκει την τιμή μιας RPN έκφρασης.
Και η πραγματικότητα είναι ότι το λογισμικό, που επιχειρεί να υπολογίσει την τιμή μιάς αλγεβρικής έκφρασης, (για παράδειγμα τις κρατήσεις υπαλλήλου σε μια μισθοδοσία), μπορεί κάλλιστα να μετατρέψει πρώτα την έκφραση σε μορφή RPN και μετά να βρει την τιμή της με διαδοχικές πράξεις.

Ας ξαναγράψουμε (δια "μαγικού τρόπου") την έκφραση του προηγούμενου παραδείγματος σε RPN μορφή :
α β γ δ ε * + * - ζ η / -
α β γ R1 + * - ζ η / -
α β R2 * - ζ η / -
α R3 - ζ η / -
R4 ζ η / -
R4 R5 -
R6

Όπως βλέπετε, γίνονται οι ίδιες πράξεις. Κάθε τελεστής εφαρμόζεται σε δύο παράγοντες/προσθετέους/κλπ αριστερά του.

Υπάρχει αλγόριθμος για μετατροπή μιάς αλγεβρικής έκφρασης σε RPN έκφραση.
Αν η αλγεβρική έκφραση δεν είναι σωστά γραμμένη, εύκολα εντοπίζεται το λάθος από τον αλγόριθμο μετατροπής (του περισσεύουν ή του λείπουν τελεστές).
Ο αλγόριθμος μετατροπής χρησιμοποιεί σωρούς (stacks) για τον χειρισμό των μεταβλητών και των τελεστών. Στον σωρό των τελεστών μπορεί να στέκεται τελεστής μεγαλύτερης ιεραρχίας πάνω από τους μικρότερης ιεραρχίας, αν όμως έρθει τελεστής μικρότερης ιεραρχίας η κλείσιμο παρένθεσης οι τελεστές βγαίνουν στον σωρό RPN.

Δείτε τον "μαγικό τρόπο" σε λειτουργία (αριστερά τα στοιχεία της έκφρασης, στη μέση [ο σωρός των τελεστών] και δεξιά [η έκφραση RPN]) :

στοιχεία της έκφρασης	ο σωρός των τελεστών	η έκφραση RPN	σχόλιο
(	(
α	(	α
-	(-	α
β	(-	αβ
*	(-*	αβ
(	(-*(	αβ
γ	(-*(	αβγ
+	(-*(+	αβγ
δ	(-*(+	αβγδ
*	(-*(+*	αβγδ
ε	(-*(+*	αβγδε
)	(-*(+*)	αβγδε	και αφού έκλεισε παρένθεση
	(-*	αβγδε*+
)	(-*)	αβγδε*+	και αφού έκλεισε παρένθεση
		αβγδε*+*-
-	-	αβγδε*+*-
ζ	-	αβγδε*+*-ζ
/	-/	αβγδε*+*-ζ
η	-/	αβγδε*+*-ζη
τέλος στοιχείων		αβγδε*+*-ζη/-

Ένα αρχαίο Fortran πρόγραμμα που έκανε στοιχειώδη μετατροπή έκφρασης σε Polish μορφή δίνεται παρακάτω :


______PROGRAM ALGPOL
C_________CASE STUDY 15 - (MAC CRACKEN ?)
C_________TRANSLATING ALGEBRAIC EXPRESSIONS TO POLISH NOTATION
______INTEGER BLANK,LPAREN,RPAREN,PLUS,MINUS,ASTRSK,SLASH,SOURCE(80),
_____1OPSTCK(80),POLISH(80),SHIER(80),OHIER(80)
______DATA BLANK,LPAREN,RPAREN,PLUS,MINUS,ASTRSK,SLASH/' ','(',')','+',
_____1'-','*','/'/
C_________
C_________INITIALIZE ARRAYS TO ZERO OR BLANK
_1001 DO 1002 L = 1, 80
______SHIER(L) = 0
______OHIER(L) = 0
______OPSTCK(L) = BLANK
______POLISH(L) = BLANK
_1002 CONTINUE
C_________READ A DATA CARD
______READ (10, 2001) SOURCE
C_________WRITE ALGEBRAIC STRING,(IN FORTRAN STYLE)
______WRITE(12, 2002) SOURCE
C_________L POINTS TO THE CURRENT CARD COLUMN
______L = 1
C_________ASSIGN HIERARCHY NUMBERS AND TEST FOR FIRST BLANK
_1003 IF(SOURCE(L) .EQ. BLANK) GO TO 1009
______IF(SOURCE(L) .EQ. LPAREN) GO TO 1004
______IF(SOURCE(L) .EQ. RPAREN) GO TO 1005
______IF(SOURCE(L) .EQ. PLUS .OR. SOURCE(L) .EQ. MINUS) GO TO 1006
______IF(SOURCE(L) .EQ. ASTRSK .OR. SOURCE(L) .EQ. SLASH) GO TO 1007
______GO TO 1008
_1004 SHIER(L) = 1
______GO TO 1008
_1005 SHIER(L) = 2
______GO TO 1008
_1006 SHIER(L) = 3
______GO TO 1008
_1007 SHIER(L) = 4
_1008 L = L + 1
______IF(L .GT. 80) GO TO 1009
______GO TO 1003
_1009 N = L - 1
C_________IF N IS NOW ZERO, CARD WAS BLANK, GO TO EXIT
______IF(N .EQ. 0) GO TO 1016
C_________INITIALIZE HIERARCHY NUMBERS
______OHIER(1) = - 1
C_________INITIALIZE POINTERS
______I = 1
______J = 2
______K = 1
C_________CHECK FOR OPERAND
_1010 IF(SHIER(I) .EQ. 0) GO TO 1012
C_________CHECK FOR RIGHT PARENTHESIS
______IF(SHIER(I) .EQ. 2) GO TO 1011
C_________OTHER OPERATOR IF HERE %% MOVE TO OPERATOR STACK
______OPSTCK(J) = SOURCE(I)
______OHIER(J) = SHIER(I)
______I = 1 + I
______J = J + 1
______GO TO 1010
C_________DELETE CORRESPONDING LEFT PARENTHESIS
_1011 I = 1 + I
______J = J - 1
______GO TO 1013
C_________MOVE OPERAND TO POLISH STRING
_1012 POLISH(K) = SOURCE(I)
______I = 1 + I
______K = K + 1
C_________CHECK HIERARCHY RANKINGS
_1013 IF (OHIER(J-1) .GE. SHIER(I)) GOTO 1014
C_________CHECK FOR END OF SOURCE STRING
______IF(I .GE. L) GO TO 1015
______GO TO 1010
C_________MOVE OPERATOR TO POLISH STRING
_1014 POLISH(K) = OPSTCK(J-1)
______K = K + 1
______J = J - 1
______GO TO 1013
C_________WRITE POLISH STRING
_1015 WRITE(12, 2003) POLISH
______GO TO 1001
C_________EXIT POINT
______STOP 1001
C_________I/O FORMATS
_2001 FORMAT(80A1)
_2002 FORMAT(* ALGEBRAIC NOTATION *,80A1)
_2003 FORMAT(* POLISH NOTATION *,80A1/)
______END


Μετατρέψτε το στην γλώσσα που χρησιμοποιείτε συνήθως και δοκιμάστε το με εκφράσεις όπως οι παρακάτω (που δεν είναι όλες αλγεβρικά σωστές!) :

A+(B/C)/(D+(E+F)/(G*H-I/(J/K+L)))-M*N
A*(B+C)
(A+B)*C
A+B*C+D
(A+B)*(C+D)
A-B/C
(A-B)/C
A/B/C
(A/B)/C
A*B/C*D/E
A*B-C+D
A*B-(C+D)
A*(B-C)+D
A*(B-C+D)
A
(((A)))
((A)+((B)))
A+B+C+D
(A+B)+(C+D)
A+B/C+D/(E+F+G-H/I)*J
(((A+B)*C+D)*E+F)*G
A+B*(C+D*(E+F*(G+H)))
AB*CD+EF-*/
AB*3.C-/BB+*

Καλή διασκέδαση!