[important_sample]

Odwrotna notacja polska i stos

#matematyka #ciekawostki #popularnonaukowe #gruparatowaniapoziomu

#mathsamples #cssamples (tagi do obserwowania)

Kojarzycie te śmieszne zagadki matematyczne, które niby mają sprawdzać znajomość kolejności wykonywania działań, np. 6÷2(2+1)? Poza uruchamianiem z wysoką skutecznością bezowocnej dyskusji w komentarzach pod postem, w którym taka zagadka się pojawia, pokazuje ona również ograniczenia notacji zapisu działań matematycznych, z której powszechnie korzystamy. Trzeba pamiętać o priorytecie działań, a jeśli chcemy zmienić ich kolejność to konieczne jest stosowanie nawiasów. Gdyby tylko istniała alternatywna notacja, w której nawiasy nie są do niczego potrzebne... ( ͡° ͜ʖ ͡°)


Przyzwyczailiśmy się do tego, żeby zapisywać działanie pomiędzy argumentami na jakich ono operuje (notacja infiksowa): 2+2. Są jednak przypadki, kiedy stosuje się inną notację, np. przy działaniu funkcji - argumenty pojawiają się po jej nazwie: f(x, y) - notacja prefiksowa. Co gdyby zapisywać tak również działania arytmetyczne? Jak można się domyślać, nie jest to nowatorski pomysł i wcześniej wpadł na niego polak Jan Łukasiewicz, przez co taka notacja jest znana jako notacja polska. Okazuje się, że jeśli liczba argumentów operatorów jest jednakowa to nie ma konieczności stosowania nawiasów. Popatrzmy na dwa wyrażenia w zwykłej notacji: "1 + 2 * 3" oraz "(1 + 2) * 3". Jeśli chcemy wymusić, aby dodawanie zostało wykonane jako pierwsze, konieczne jest postawienie nawiasu. W notacji polskiej możemy zapisać oba wyrażenia bez większych problemów: "+ * 2 3 1" i "* + 1 2 3". Pierwsze z wyrażenie należy czytać tak: "+(*(2, 3), 1)" - traktujemy działania jakby były funkcjami. W drugim wyrażeniu mamy zaś "*(+(1, 2), 3)". W obu przypadkach kolejność wykonywania działań jest zgodna z intencją.

Tak jak Charmander ewoluuje w Charmeleona, tak notacja polska ma swojego następnika w postaci (lepszej) odwrotnej notacji polskiej (RPN) ( ͡° ͜ʖ ͡°) Okazuje się, że notacja staje się jeszcze przydatniejsza, jeśli wywalimy działania na koniec, za argumenty. Wtedy "2 * x + 6" zapiszemy jako "2 x * 6 +" - i to jest OK ( ͡° ͜ʖ ͡°)

Jako zwykli śmiertelnicy w ludzkich powłokach możemy nie dostrzegać zalet takiej notacji, ale komputery aż przebierają rdzeniami na myśl o tym, jak będą ewaluować tak zapisane działania! W zrozumieniu dlaczego taki zapis jest dla nich koszerny pomoże nam stos.

Stos to taka struktura danych agregująca elementy, która pozwala na dodawanie i usuwanie jedynie z góry stosu (push i pop). Najlepszym porównaniem do czegoś, co zna każdy z nas może być kupka wstydu (Tsundoku po japońsku). Włożenie książki w środek stosu jest dosyć kłopotliwe, więc kładziemy ją na szczyt. Podobnie jest z wyjmowaniem książki ze środka.

Tym razem, zamiast książek, na stos będziemy kłaść argumenty działań i ich wyniki. Dla oszczędności miejsca stos będę zapisywał bokiem, a spód stosu (stół w analogii z książkami) oznaczony będzie za pomocą |:

| książka1 książka2 książka3

na szczycie stosu jest książka3.

Ewaluacja wyrażeń w odwrotnej notacji polskiej polegać będzie na czytaniu wyrażenia od lewej do prawej i wrzucaniu na stos argumentów. Jeśli natkniemy się na operator (np. dodawanie czy mnożenie) to zdejmiemy ze stosu tyle elementów, ile dane działanie wymaga (w tym przypadku dwa), wykonamy to działanie i wynik wrzucimy z powrotem na stos. Zobaczmy to na przykładzie wyrażenia "1 + 2 * 3", które w odwrotnej notacji polskiej odpowiada "1 2 3 * +":

Po przeczytaniu pierwszych trzech liczb stos wygląda jak niżej:

| 1 2 3

i trafiamy na pierwsze działanie, jakim jest mnożenie. Zdejmujemy więc ze stosu dwie pierwsze liczby czyli 3 i 2 (w tej kolejnosci!) i wykonujemy na nich mnożenie. Otrzymany wynik wrzucamy na stos i kontynuujemy działanie:

| 1 6

Ostatni symbol wejściowy to '+', więc zdejmujemy ze stosu dwie liczby i je dodajemy. Wynik wrzucamy na stos:

| 7

Ze względu na to, że na wejściu nie ma już żadnych innych działań ani liczb to kończymy ewaluowanie, odczytując wynik wyrażenia ze stosu. Można sprawdzić, że rzeczywiście "1 + 2 * 3" to 7.

Jak widać wykonywanie działań zapisanych w odwrotnej notacji polskiej jest wręcz trywialne. Dodatkowo, bardzo łatwo jest wykryć niepoprawne wyrażenia: jeśli natrafimy na operator, a na stosie nie będzie wystarczająco dużo argumentów, to wyrażenie było niepoprawnie skonstruowane (np. "2 2 + +"). Stworzenie programu, który czyta tak zapisane wyrażenia jest dużo łatwiejsze niż w przypadku zwykłej notacji infiksowej - wtedy trzeba się bawić w bardziej skomplikowane parsowanie (o tym i o gramatyce języka formalnego może innym razem).

Poniżej (uproszczona) implementacja w #python:

expr = "1 2 3 * +"

stack = []

for atom_str in expr.split():
    atom_stripped = atom_str.strip()  # remove excess spaces

    if atom_stripped == '+':
        if len(stack) < 2:
            print("Invalid expression!")
            break

        b = stack.pop()
        a = stack.pop()

        stack.append(a + b)

    elif atom_stripped == '*':
        if len(stack) < 2:
            print("Invalid expression!")
            break

        b = stack.pop()
        a = stack.pop()

        stack.append(a * b)
    else:
        stack.append(int(atom_stripped))

if len(stack) == 1:
    print(f"Result: {stack.pop()}")

W ramach ciekawostki mogę powiedzieć, że notacja polska (nie odwrócona) jest stosowana w językach z rodziny LISP.

[Lachon]

@important_sample: i takie rzeczy o 6 rano trzeba plusować !

[important_sample]

@Lachon: testuję jaka godzina jest najlepsza na wrzucanie ( ͡° ͜ʖ ͡°)

[Rasteris]

@important_sample: FORTH też korzystał z tego albo węgierskiej.

[Poldek0000]

@important_sample
Tekst rozbudził mnie bardziej niż kawa.

[important_sample]

@Rasteris: zgadza się! ogólnie języki stosowe z niej korzystają - zapomniałem o tym wspomnieć.

fun fact: znany streamer Tsoding zrobił własny self-hosted turing complete język stosowy o nazwie Porth, bo pierwszy interpreter był pisany w Pythonie ( ͡° ͜ʖ ͡°)

[czotoco]

@important_sample: o co chodzi ze zdjęciem załączonym do wpisu?
Edit: dobra już się obudziłem :D

[important_sample]

@czotoco: ukradłem z wcześniejszego wpisu na tagu ( ͡° ͜ʖ ͡°)

jedni liczą 6÷2(2+1) z lewej do prawej i wychodzi im 9 a inni grupują 2(2+1) jakby było razem w mianowniku i wychodzi 1

[pepepanpatryk]

@important_sample: bardzo ciekawe, plusik!

[sruba_m3]

@important_sample korzystam na kalkulatorze na telefonie od lat, już nie umiem liczyć na zwykłym kalkulatorze xD

[TwujKoshmar]

@important_sample nic nie rozumiem ale plusik za chęci

[mirabelka2137]

Taktyk

[K-S-]

@important_sample: dawno nie widziałem tu tak dobrego wpisu.

[Borysko_88]

@important_sample na podstawach programowania na studiach pisałem to w C. To byli czasy. Ile się człowiek nawyklinał gdy po raz n-ty poleciał Segmentation fault to głowa mała ( ͡º ͜ʖ͡º)

[wda79]

@important_sample: Podobno jak na kalkulatorze dodasz znak mnożenia między dwójką i nawiasem, to też wyjdzie 9.

[zapster]

Było i na czarno

[koniecswiatajestbliski]

@important_sample: 9

[apeee]

@important_sample: tl;dr

[grzesiek_888]

ale komputery aż przebierają rdzeniami na myśl o tym, jak będą ewaluować tak zapisane działania

@important_sample: ale kekłem xD

[FiranMercury]

@important_sample czuję się jakbym cofnął się w czasie 10 lat. Nawet chyba poczułem zapach swojego starego komputera.
Wykop kiedyś taki był

[vartan]

@important_sample Casio do w-------a