G. Jagiella

Skrypt do wykładu Programowanie 2 (Python)

ostatnia modyfikacja: 09.03.2021

Wykład 3 (cz. 1): odwrotna notacja polska (Reverse Polish Notation)¶

Spis treści¶

Notacje funkcyjne
Wyrażenia arytmetyczne i notacja polska
Odwrotna notacja polska

Notacje funkcyjne ¶

Niech $f \colon A \times B \to C$ będzie funkcją. W zwykłej notacji wartość $f$ z argumentami $a \in A, b \in B$ piszemy $$f(a, b).$$ Alternatywną notacją jest pisanie nazwy funkcji po jej argumentach: $$(a, b)f.$$ Kolejność argumentów nie ulega zmianie: pierwszym jest $a$, drugim $b$. Podobnie dla funkcji dowolnie wielu zmiennych: $$(a, b, c)g, \\ (x)\sin.$$ Wyrażenie zapisane w zwykłej notacji jako $f(g(a,b,c), \sin(x))$ w alternatywnej notacji ma postać $((a,b,c)g, (x)\sin)f$.

Wyrażenia arytmetyczne i notacja polska ¶

W standardowej notacji arytmetycznej, operatory stawiamy pomiędzy ich argumentami.

Kolejność wykonywania działań w standardowej notacji zależy od:

Priorytetów operatorów. Operacje multiplikatywne (np. $\cdot, /$) wykonujemy przez addytywnymi (np. $+, -$). Potęgowanie (^ lub $**$) wykonujemy przed operacjami multiplikatywnymi.
Łączności operatorów. Operacje tego samego typu wykonujemy zgodnie z ich łącznością. Operatory $+, \cdot$ są obustronnie łączne. Operatory $-, /$ są łączne lewostronnie, ale nie prawostronnie. Operacja potęgowania jest łączna prawostronnie, ale nie lewostronnie ($a$ ^ $b$ ^ $c = a$ ^ $(b$ ^ $c)$).
Nawiasów.

To całkiem sporo reguł, z których 1. i 2. nie są częścią samej notacji, a konwencją. Istnieją inne sposoby zapisu wyrażeń arytmetycznych, które eliminują te konwencje (i nie uzywają nawiasów).

Każdą operację arytmetyczną możemy traktować jako funkcję dwóch argumentów, której wartością jest liczba rzeczywista, tzn. $$\circ \colon \mathbb{R} \times \mathbb{R} \to \mathbb{R},$$ gdzie $\circ$ to dowolny operator arytmetyczny, np. $+, -, \cdot, /$ (ignorujemy tutaj problem dzielenia przez zero). W ten sposób możemy zapisać dowolne wyrażenie arytmetyczne w postaci funkcyjnej, np.

Wyrażenie	Postać funkcyjna
$2 + 2$	$+(2, 2)$
$1 + 2 \cdot a$	$+(1, \cdot(2, a))$
$(1 - 2) \cdot (3 / 4)$	$\cdot(-(1, 2), /(3, 4))$

W zapisie funkcyjnym, oprócz symboli funkcji oraz ich argumentów pojawiają się dodatkowe symbole: nawiasy obejmujące argumenty funkcji oraz oddzielające je przecinki. Jak zaraz udowodnimy, interesującą własnością funkcyjnego zapisu wyrażenia jest to, że jest on jednoznaczny nawet po usunięciu tych dodatkowych symboli. Napis powstały po ich usunięciu nazwiemy zapisem wyrażenia w notacji polskiej (NP; ang. Polish Notation, PN). W ten sposób:

Wyrażenie	Postać funkcyjna	Postać NP
$2 + 2$	$+(2, 2)$	`+ 2 2`
$1 + 2 \cdot a$	$+(1, \cdot(2, a))$	`+ 1 * 2 a`
$(1 - 2) \cdot (3 / 4)$	$\cdot(-(1, 2), /(3, 4))$	`* - 1 2 / 3 4`

Ustalmy pewną terminologię. Token to: liczba rzeczywista, symbol (stała oznaczająca liczbę), nawias (lewy lub prawy), lub operator arytmetyczny. Ograniczymy się tutaj do czterech podstawowych operatorów: $+, -, \cdot, /$. Zauważmy, że wszystkie są lewostronnie łączne.

Zarówno wyrażenia w zwykłej notacji arytmetycznej, jak i wyrażenia NP są ciągiem tokenów. Długość wyrażenia to ilość tokenów w ciągu. Oczywiście nie każdy ciąg tokenów jest poprawnym wyrażeniem w jednej lub drugiej notacji.

Dla ciągu tokenów $S$, jego odcinkiem początkowym (lub prefiksem) nazwiemy ciąg tokenów $S'$ powstały z usunięcia z $S$ pewnej ilości końcowych tokenów. W szczególności $S$ jest swoim własnym odcinkiem początkowym.

Udowodnimy teraz, że usunięcie nawiasów i przecinków z zapisu funkcyjnego nie sprawia, że wyrażenie przestaje być jednoznaczne.

Twierdzenie. Zapis w NP jest jednocznaczny.
Dowód. Jeśli wyrażenie NP jest długości $1$, to jest liczbą lub symbolem, więc jest jednoznaczne. Dla $n > 1$ udowodnimy indukcyjnie następujące dwie własności: 1) Jeśli $S$ i $S'$ są wyrażeniami NP długości co najwyżej $n$, a $S'$ jest odcinkiem początkowym $S$, to $S' = S$.
2) Jeśli $S$ jest wyrażeniem NP długości $n$, to istnieje dokładnie jedna para $L, R$ wyrażeń NP taka, że $S = \circ ~ L ~ R$, gdzie $\circ$ jest operatorem. Ustalmy $n > 1$ i załóżmy, że 1) i 2) są prawdziwe dla wyrażeń długości $k < n$. Ustalmy wyrażenie NP $S$ długości $n > 1$. Jest ono postaci $S = \circ ~L ~ R$ dla pewnych wyrażeń NP $L, R$ długości mniejszej niż $n$ oraz operatora $\circ$. Niech $S'$ to odcinek początkowy $S$ będący wyrażeniem NP. Długość $S'$ nie może być równa $1$, zatem $S'$ jest postaci $S' = \circ ~ L' ~ R'$ dla pewnych wyrażeń NP $L', R'$ długości mniejszej niż $n$. Wtedy $L$ jest odcinkiem początkowym $L'$ lub $L'$ jest odcinkiem początkowym $L$. Z założenia indukcyjnego (punkt 1)), $L = L'$. Stąd $R'$ jest odcinkiem początkowym $R$ i podobnie $R = R'$. Zatem również $S = S'$. To pokazuje, że punkty 1) i 2) zachodzą dla $n$. $\dashv$

Uwaga. Definicja wyrażeń NP ma sens dla wyrażeń innych niż arytmetyczne, a odpowiednik powyższego twierdzenia też jest dla nich prawdziwy. Przykładowo, zapis funkcyjny $f(g(a,b,c), \sin(x))$ w notacji NP zapisze się jako:

f g a b c sin x i napis ten da się odczytać jednoznacznie, o ile znane są ilości argumentów występujących w nim funkcji.

Przykłady: 1)

+ * A B * C D + * A B * C D
W notacji zwykłej: A * B + C * D
2) - * + A B C * - D E + F G - * + A B C * - D E + F G - * + A B C * - D E + F G
W notacji zwykłej: ( A + B ) * C - ( D - E ) * ( F + G )

Odwrotna notacja polska ¶

Wstęp ¶

W notacji polskiej wyrażeń arytmetycznych, operatory piszemy przed ich argumentami. Alternatywnie, operatory te moglibyśmy pisać za argumentami.

Ściślej: możemy zapisać wyrażenie arytmetyczne w postaci funkcyjnej, stosując alternatywną notację z początku notatek. Wtedy wyrażenie $2+2$ zapiszemy jako $(2,2)+$, natomiast $a \cdot (2 + b)$ jako $(a, (2, b)+)\cdot$. Okazuje się, że tak jak w przypadku zwykłej notacji funkcyjnej, nawiasy i przecinki są zbędne do określenia argumentów wszystkich operacji (odpowiednik twierdzenia dla NP jest prawdziwy). Gdy opuścimy te symbole, otrzymamy zapis wyrażenia w odwrotnej notacji polskiej (ONP; ang. Reverse Polish Notation, RPN). Tak jak dla pozostałych notacji, traktujemy go jako ciąg tokenów.

Wyrażenie	Postać ONP (RPN)
$2 + 2$	`2 2 +`
$1 + 2 \cdot a$	`1 2 a * +`
$(1 - 2) \cdot (3 / 4)$	`1 2 - 3 4 / *`

Przykłady: 1)

7 8 + 3 A + * 7 8 + 3 A + *
W notacji zwykłej: ( 7 + 8 ) * ( 3 + A )
2) 1 2 3 4 + + + 1 2 3 4 + + + 1 2 3 4 + + + W notacji zwykłej: 1 + ( 2 + ( 3 + 4 ) ) = 1 + 2 + 3 + 4

Wyliczanie wyrażeń odwrotnej notacji polskiej ¶

Teraz przyjmijmy, że w wyrażeniach ONP nie pojawiają się tokeny oznaczające stałe (a więc wyrażenia składają się tylko z operatorów i liczb).

Wyrażenia ONP możemy wyliczać tak, jak odpowiadające im postacie funkcyjne. Podwyrażenia ONP można zastępować ich wartościami, otrzymując wyrażenie ONP o tej samej wartości, co oryginalne, ale zawierające mniej operatorów.
Przykład:

7 8 + 3 6 + * = 7 8 + 3 6 + * = 7 8 + 9 * = 7 8 + 9 * = 15 9 * = 135

Wyliczając wartość operacji w wyrażeniu ONP trzeba znać wartość jego argumentów. Może to nie być proste, jeśli same są podwyrażeniami zawierającymi operacje (w szczególności wyliczenie wartości ostatniej operacji w wyrażeniu RPN to nic innego, jak wyliczenie wartości całego wyrażenia). Jeśli jednak dwa tokeny na lewo od tokenu-operatora są liczbami, to trzy tokeny są pojedynczym wyrażeniem i ich wartość można łatwo obliczyć, np:

5 6 - 4 * 5 2 2 * - - = 5 6 - 4 * 5 2 2 * - - = 5 6 - 4 * 5 4 - - = 5 6 - 4 * 5 4 - - = 5 6 - 4 * 1 - = 5 6 - 4 * 1 - = -1 4 * 1 - = -1 4 * 1 - = -4 1 - = -5

Podstawienia wartości podwyrażeń można dokonywać w dowolnej kolejności. Zauważmy jednak, że pierwszy (najbardziej po lewej) token-operator w wyrażeniu ONP nigdy nie może mieć argumentów, które nie są liczbami, zatem wyliczanie wyrażenia można usystematyzować, wyliczając wartości operatorów "od lewej do prawej", np.:

5 6 - 4 * 5 2 2 * - - = 5 6 - 4 * 5 2 2 * - - = -1 4 * 5 2 2 * - - = -1 4 * 5 2 2 * - - = -4 5 2 2 * - - = -4 5 2 2 * - - = -4 5 4 - - = -4 5 4 - - = -4 1 - = -5

Teraz przetłumaczymy powyższą procedurę na algorytm, którego wejściem jest ciąg tokenów kodujący wyrażenie ONP. Rozważmy pionową kreskę, poruszającą się przez kolejne tokeny wejściowe, która po napotkaniu tokena-operatora wykonuje stosowne działanie arytmetyczne:

| 5 6 - 4 * 5 2 2 * - - 5 | 6 - 4 * 5 2 2 * - - 5 6 | - 4 * 5 2 2 * - - -1 | 4 * 5 2 2 * - - -1 4 | * 5 2 2 * - - -4 | 5 2 2 * - - -4 5 | 2 2 * - - -4 5 2 | 2 * - - -4 5 2 2 | * - - -4 5 4 | - - -4 1 | - -5 |

Niech w naszym algorytmie liczby z lewej strony kreski będą reprezentowane przez stos (rosnący od lewej, do prawej). Wtedy algorytm można przetłumaczyć na następujące kroki:

Kroki ewaluacji wyrażeń ONP (wejście - ciąg tokenów):

Stwórz pusty stos.

Dla każdego kolejnego tokenu z wejścia:
2a. Jeśli tokenem jest liczba: połóż ją na stos.
2b. Jeśli tokenem jest operator $\circ$: ściągnij ze stosu prawy argument $b$, ściągnij ze stosu lewy argument $a$, wykonaj obliczenie $a \circ b$, połóż wynik na stos.

Ściągnij ze stosu i zwróć wynik obliczenia.

Zauważmy, ze wszystkie instrukcje kroku 2 mają stałą złożoność. Stąd złożoność obliczeniowa tego algorytmu to $\Theta(n)$, gdzie $n$ to ilość tokenów na wejściu. Kod algorytmu (w którym ograniczamy się jedynie do operacji całkowitoliczbowych):

from stack import Stack

def postfix_eval(postfix_expr): # "2 3 +"
    operand_stack = Stack()

    for token in postfix_expr.split():
        if token in '+-*/':
            b = operand_stack.pop()
            a = operand_stack.pop()
            result = do_math(token, a, b)
            operand_stack.push(result)
        else:
            operand_stack.push(int(token))
            
    return operand_stack.pop()

def do_math(op, a, b):
    if op == "*":
        return a * b
    elif op == "/":
        return a // b
    elif op == "+":
        return a + b
    else:
        return a - b

postfix_eval("5 6 - 4 * 5 2 2 * - -")

-5

ONP ma sporo zalet nad zwykłą notacją: brak nawiasów, brak priorytetów operatorów (działania można wykonywać od lewej do prawej), łączność operacji jest nieistotna. Jednym z jej zastosowań, które teraz omówimy, jest wyliczanie wyrażeń arytmetycznych zapisanej w zwykłej notacji.

Konwersja do ONP: Shunting Yard Algorithm ¶

Wyrażenia arytmetyczne w zwykłej notacji można algorytmicznie wyliczyć w bezpośredni sposób. Zamiast tego, podamy (bez dowodu, z uzasadnieniami) algorytm konwersji wyrażeń w zwykłej notacji do wyrażeń ONP. Ten algorytm, połączony z algorytmem wyliczania wyrażeń ONP, pozwala na wyliczenie wartości dowolnego wyrażenia w zwykłej notacji.

Wejściem algorytmu będzie ciąg tokenków, kodujący wyrażenie w zwykłej notacji. Wyjściem będzie ciąg tokenów kodujący to samo wyrażenie w ONP. Dopuszczamy tokeny reprezentujące stałe, a więc argumentami operatorów, które nie są podwyrażeniami (tzw. operandami) mogą być zarówno liczby, jak i stałe.

Algorytm działa na zasadzie analogii z kolejową stacją rozrządową (stąd nazwa: Shunting Yard Algorithm):

Źródło obrazu: Wikipedia.org, na licencji Creative Commons

Tokeny z wejścia reprezentowane są jako wagony, poruszający się po górnym torze. Prawa strona toru zawiera tokeny wejściowe. Lewa strona przeznaczona jest na tokeny wyjściowe. Wagony-tokeny mogą być przemieszczane z wejscia do wyjścia po górnym torze. Mogą jednak korzystać z dolnego, "bocznego" toru. Dolny tor działa na zasadzie stosu: wagon, który na niego wjedzie blokuje wagony, które wjechały tam wcześniej. Algorytm, dla każdego tokenu na wejściu, kieruje go na wyjście lub na dolny tor, z którego może on później pojechać na wyjście. Po zakończeniu algorytmu, wszystkie wagony-tokeny z wejścia są przemieszczone na wyjście, za wyjątkiem tokenów reprezentujących nawiasy.

Jedynymi tokenami, które trafiają na dolny tor są operatory i lewe nawiasy, dlatego stos reprezentujący dolny tor nazywamy stosem operatorów. Kroki algorytmu są następujące:

Kroki konwersji do ONP (wejście - ciąg tokenów)

Stwórz pusty stos operatorów (dolny tor)

Dla każdego tokenu z wejścia:
2a. Jeśli tokenem jest liczba lub stała: połóż ten token na wyjście.
2b. Jeśli tokenem jest (: połóż go na stos operatorów.
2c. Jeśli tokenem jest ): przesuwaj operatory ze stosu na wyjście, dopóki na szczycie stosu nie pojawi się (; wtedy usuń ( ze stosu.
2d. Jeśli tokenem jest operator $\circ$: dopóki na szczycie stosu znajduje się operator o priorytecie wyższym lub równym od priorytetu $\circ$, ściągaj operatory ze stosu na wyjście; następnie połóż $\circ$ na stosie.

Dopóki stos nie jest pusty, ściągaj operatory ze stosu na wyjście.

Uwagi dotyczące algorytmu: 1) Jego złożonością jest $\Theta(n)$, gdzie $n$ to długość wyrażenia na wejściu.
2) Operandy w wyjściowym wyrażeniu ONP stoją w ten samej kolejności, co w wyrażeniu wejściowym.
3) Operatory występujące po otwierającym nawiasie trafią na wyjście nie później, niż w momencie napotkania na wejściu odpowiadającemu mu nawiasowi zamykającemu. W konsekwencji podczas obliczania wyjściowego wyrażenia ONP zostaną one obliczone przed operatorami spoza nawiasów (zgodnie z oczekiwaniem!).
4) Ściąganie operatorów w kroku 2d) gwarantuje, że działania będą wykonywane zgodnie z priorytetem, a w przypadku działań o równym priorytecie, od lewej do prawej.

Poniżej kod algorytmu:

def infix_to_postfix(infix_expr):
    prec = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}

    op_stack = Stack() # Stos operatorow
    postfix = [] # Wyjscie

    for token in infix_expr.split():
        if token.isalnum():
            postfix.append(token)
        elif token == "(":
            op_stack.push(token)
        elif token == ")":
            while op_stack.peek() != '(':
                postfix.append(op_stack.pop())

            op_stack.pop() # Zrzucenie '(' ze stosu
        else:
            while not op_stack.is_empty() and prec[op_stack.peek()] >= prec[token]:
                postfix.append(op_stack.pop())
            op_stack.push(token)

    while not op_stack.is_empty():
        postfix.append(op_stack.pop())

    return " ".join(postfix)

print(infix_to_postfix("A * B + C * D"))
print(infix_to_postfix("( A + B ) * C - ( D - E ) * ( F + G )"))
print(infix_to_postfix("( 5 - 6 ) * 4 - ( 5 - 2 * 2 )"))
print(infix_to_postfix("( 7 + 8 ) / ( 3 + 2 )"))

A B * C D * +
A B + C * D E - F G + * -
5 6 - 4 * 5 2 2 * - -
7 8 + 3 2 + /

A niżej: użycie obu napisanych funkcji do ewaluacji wyrażeń w zwykłej notacji:

print(postfix_eval(infix_to_postfix("( 5 - 6 ) * 4 - ( 5 - 2 * 2 )")))
print(postfix_eval(infix_to_postfix("( 7 + 8 ) / ( 3 + 2 )")))

-5
3

Wykład 3 (cz. 1): odwrotna notacja polska (Reverse Polish Notation)¶

Spis treści¶

Notacje funkcyjne¶

Wyrażenia arytmetyczne i notacja polska¶

Odwrotna notacja polska¶

Wstęp¶