Evaluate Reverse Polish Notation

Q: Jaka jest złożoność czasowa obliczania wyrażenia w odwrotnej notacji polskiej?

Rozwiązanie ze stosem działa w czasie O(n) dla n tokenów: każda liczba jest umieszczana na stosie raz, a każdy operator wykonuje dwa zdjęcia ze stosu i jedno umieszczenie na stosie. Stos może przechowywać do około n/2 wartości, więc zużycie pamięci wynosi O(n) . Wielokrotne upraszczanie pierwszego operatora zajmuje O(n²) czasu, ponieważ w każdej rundzie wyszukiwanie zaczyna się od początku.

Q: Dlaczego odwrotna notacja polska nie wymaga nawiasów?

W zwykłym zapisie wyrażenie 3 + 4 * 2 wymaga reguły pierwszeństwa lub nawiasów, aby określić, które działanie wykonać jako pierwsze. W odwrotnej notacji polskiej operator zawsze działa na dwóch wartościach bezpośrednio przed nim, więc kolejność tokenów mówi wszystko: 3 4 2 * + daje 11, a 3 4 + 2 * daje 14. Dlatego do obliczenia wyrażenia wystarczy jeden stos i nie trzeba nigdy zaglądać naprzód.

Q: Jak dzielić w Pythonie z zaokrąglaniem w kierunku zera?

Użyj int(a / b) . Operator // zaokrągla w dół, więc -7 // 2 daje -4, a int(-7 / 2) daje -3. Dzielenie zmiennoprzecinkowe jest tutaj wystarczająco dokładne, ponieważ wartości mieszczą się w 32 bitach. W przypadku dowolnie dużych liczb całkowitych podziel wartości bezwzględne za pomocą // , a następnie przywróć znak.

ŚrednieStos

+10

Otrzymujesz wyrażenie arytmetyczne w odwrotnej notacji polskiej w postaci tablicy tokenów. W tej notacji każdy operator występuje zaraz po swoich dwóch operandach, więc 3 4 + oznacza 3 + 4, a 3 4 + 2 * oznacza (3 + 4) * 2 — nawiasy nie są potrzebne. Każdy token jest liczbą całkowitą albo jednym z operatorów +, -, * i /.

Oblicz wartość wyrażenia i ją zwróć. Dzielenie zachowuje tylko część całkowitą i zaokrągla w kierunku zera: 7 / 2 to 3, a -7 / 2 to -3.

Funkcja

evalRPN(tokens: string-array) → integer

tokensstring-array: liczby i operatory wyrażenia, w podanej kolejności
Zwracainteger: wartość wyrażenia

Ograniczenia

1 ≤ tokens.length ≤ 10⁴
Każdy token to +, -, *, / lub liczba całkowita z zakresu od -200 do 200, zapisana w systemie dziesiętnym, z poprzedzającym minusem, jeśli jest ujemna.
tokens jest poprawnym wyrażeniem w odwrotnej notacji polskiej.
Nie dochodzi do dzielenia przez zero, a każda wartość pośrednia i końcowa jest większa niż -2³¹ i mniejsza niż 2³¹.

Przykłady

Wejście: tokens = ["8", "3", "-", "4", "*"]
Wyjście: 20
Wyjaśnienie: Operator - działa na dwóch liczbach przed nim w ich kolejności: najpierw 8, potem 3, więc daje 5, a nie -5. Następnie * mnoży tę 5 przez 4, co daje 20.

Wejście: tokens = ["6", "2", "9", "3", "/", "-", "*"]
Wyjście: -6
Wyjaśnienie: Pierwszy operator, /, używa dwóch ostatnich wartości: 9 podzielone przez 3 daje 3. Następnie - oblicza 2 minus to 3, co daje -1, a * mnoży 6 przez -1.

Wejście: tokens = ["10", "-7", "2", "/", "+"]
Wyjście: 7
Wyjaśnienie: Żeton -7 to liczba, a nie operator. -7 podzielone przez 2 to -3.5, co po obcięciu w kierunku zera daje -3, a nie zaokrągleniu w dół do -4, a 10 plus -3 to 7.

+18 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz odtworzyć wyrażenie w zwykłej notacji, na przykład (3 + 4) * 2, dodając nawiasy tylko tam, gdzie zmieniają znaczenie?

Rozwiązanie

Notacja polska odwrotna nie wymaga nawiasów, ponieważ kolejność tokenów już ustala kolejność działań: każdy operator działa na dwóch wartościach znajdujących się bezpośrednio przed nim, a każda z tych wartości może być wynikiem wcześniejszego operatora. Stos wartości pozwala obliczyć całe wyrażenie w jednym przebiegu od lewej do prawej. Pułapki tkwią w szczegółach: kolejność operandów dla - i /, odróżnianie operatora - od liczby -7 oraz dzielenie, które zaokrągla w kierunku zera.

Zwiń pierwszy operator, powtórz

Poprawne, ale nie kończy się na największych testach

Intuicja

Tak wyglądałoby rozwiązywanie tego na papierze. Znajdź operator najbardziej po lewej stronie. Żaden operator nie znajduje się przed nim, więc dwa tokeny bezpośrednio przed nim to zwykłe liczby, które są jego operandami. Oblicz wynik i zastąp te trzy tokeny jedną liczbą. Wyrażenie jest teraz krótsze i nadal oznacza to samo. Powtarzaj, aż zostanie jedna liczba.

Weź ["6", "2", "9", "3", "/", "-", "*"]. Pierwszym operatorem jest /, więc 9 3 / daje 3: ["6", "2", "3", "-", "*"]. Następnie 2 3 - daje -1: ["6", "-1", "*"]. Potem 6 -1 * daje -6 — to odpowiedź.

Jest to poprawne, ponieważ w każdej rundzie kompletny fragment a b op zostaje zastąpiony swoją wartością, a operatory znajdujące się za nim widzą tę wartość dokładnie tam, gdzie znajdował się fragment. Jest to powolne, ponieważ w każdej rundzie wyszukiwanie zaczyna się od początku, a następnie zamyka lukę w środku tablicy. Przy 5,000 liczbach, po których następuje 4,999 operatorów, pierwszy operator znajduje się mniej więcej w połowie, przez wszystkie 4,999 rund, więc same wyszukiwania sprawdzają około 1.25 × 10^7 tokenów. Liczby po lewej stronie operatora prawie się nie zmieniają między kolejnymi rundami, a mimo to w każdej rundzie są ponownie odczytywane.

Algorytm

Skopiuj tokeny na listę, którą możesz modyfikować.
Przeszukuj listę od początku do pierwszego operatora, na pozycji k.
Zastosuj go do liczb na pozycjach k-2 (po lewej) i k-1 (po prawej).
Zastąp trzy tokeny na pozycjach k-2, k-1 i k wynikiem.
Powtarzaj, aż zostanie jeden token, i zwróć go jako liczbę.

def evalRPN(tokens):
    items = list(tokens)
    while len(items) > 1:
        # Find the first operator. Everything to its left is a plain number.
        k = 0
        while items[k] not in ("+", "-", "*", "/"):
            k += 1
        left, right, op = int(items[k - 2]), int(items[k - 1]), items[k]
        if op == "+":
            value = left + right
        elif op == "-":
            value = left - right
        elif op == "*":
            value = left * right
        else:
            value = int(left / right)  # int() truncates toward zero
        # Replace the three tokens "left right op" with the number they stand for.
        items[k - 2:k + 1] = [str(value)]
    return int(items[0])

Jedno przejście ze stosem wartości

Intuicja

Metoda redukcji wymaga ponownego odczytywania liczb znajdujących się na lewo od operatora. Zamiast tego umieść je na stosie. Odczytuj tokeny tylko raz, od lewej do prawej. Liczba trafia na stos. Operator zdejmuje ze stosu dwie wartości z wierzchu, łączy je i odkłada wynik z powrotem, gdzie czeka na następny operator jak każda inna wartość.

Prześledźmy ["6", "2", "9", "3", "/", "-", "*"]. Cztery liczby trafiają na stos: [6, 2, 9, 3]. Operator / zdejmuje 3, a potem 9, i odkłada 9 / 3 = 3: [6, 2, 3]. Operator - zdejmuje 3, a potem 2, i odkłada 2 - 3 = -1: [6, -1]. Operator * zdejmuje -1, a potem 6, i odkłada 6 * -1 = -6. Pozostaje jedna wartość i jest nią wynik.

Dlaczego to działa: w każdej chwili stos zawiera wartości kompletnych fragmentów odczytanych do tej pory, w odpowiedniej kolejności, a operator zawsze działa na dwóch ostatnich z nich. Szczyt stosu to prawy operand, ponieważ został utworzony jako ostatni, więc zdejmij go jako pierwszy. Pomylenie tej kolejności ujawnia się tylko przy - i /, gdzie 8 3 - musi dawać 5, a nie -5.

Dzielenie wymaga ostrożności w niektórych językach. Wyrażenie zaokrągla w kierunku zera, ale operator // w Pythonie, / w Ruby i %/% w R zaokrąglają w dół, przez co -3.5 zmienia się w -4. Każda liczba jest odkładana raz, a każdy operator zdejmuje dwie wartości i odkłada jedną, więc przejście zajmuje O(n) czasu, a na stosie nigdy nie ma więcej niż n wartości.

Algorytm

Zacznij od pustego stosu.
Dla każdego tokenu będącego liczbą umieść jego wartość na stosie.
Dla każdego operatora zdejmij najpierw prawy operand, a następnie lewy operand.
Oblicz left op right, zaokrąglając wynik dzielenia / w kierunku zera, i umieść wynik na stosie.
Po ostatnim tokenie zwróć jedyną wartość na stosie.

def evalRPN(tokens):
    stack = []  # values of the parts read so far, the newest on top
    for token in tokens:
        if token in ("+", "-", "*", "/"):
            # The right operand was pushed last, so it comes off first.
            right = stack.pop()
            left = stack.pop()
            if token == "+":
                stack.append(left + right)
            elif token == "-":
                stack.append(left - right)
            elif token == "*":
                stack.append(left * right)
            else:
                # int() truncates toward zero; // would round -7 / 2 down to -4.
                stack.append(int(left / right))
        else:
            stack.append(int(token))
    return stack[0]

Pułapki i przypadki brzegowe

Pętla stosu jest krótka; większość błędnych odpowiedzi wynika z kolejności operandów oraz ze sposobu, w jaki dany język wykonuje dzielenie.

Zamiana operandów miejscami. Pierwszy zdjęty ze stosu operand jest prawym operandem: ["3", "5", "-"] to -2, a ["2", "9", "/"] to 0, nie 4.
Rozpoznawanie operatorów na podstawie pierwszego znaku. -7 zaczyna się od znaku minus, ale jest liczbą. Porównaj cały token albo sprawdź, czy ma jeden znak.
Zaokrąglanie w dół zamiast obcinania części ułamkowej. -7 / 2 musi dać -3, a -1 / 3 musi dać 0. Operator // w Pythonie, / w Ruby, %/% w R i math.floor w Lua dają -4 i -1.
Wyświetlanie -0. W JavaScript i Lua każda liczba jest liczbą zmiennoprzecinkową, więc 0 * -5 i Math.trunc(-1 / 3) dają ujemne zero, które jest wyświetlane jako -0. Dodaj 0 do końcowej wartości, aby zamienić ją na 0.
Odczytywanie liczby po jednej cyfrze. Tokeny takie jak 13 i -200 mają kilka znaków; sparsuj cały token.
Zakładanie, że ostatni token jest operatorem. Pojedyncza liczba, taka jak ["7"], jest prawidłowym wyrażeniem o wartości 7.

Najczęstsze pytania4

Jaka jest złożoność czasowa obliczania wyrażenia w odwrotnej notacji polskiej?

Rozwiązanie ze stosem działa w czasie O(n) dla n tokenów: każda liczba jest umieszczana na stosie raz, a każdy operator wykonuje dwa zdjęcia ze stosu i jedno umieszczenie na stosie. Stos może przechowywać do około n/2 wartości, więc zużycie pamięci wynosi O(n). Wielokrotne upraszczanie pierwszego operatora zajmuje O(n²) czasu, ponieważ w każdej rundzie wyszukiwanie zaczyna się od początku.

Dlaczego odwrotna notacja polska nie wymaga nawiasów?

W zwykłym zapisie wyrażenie 3 + 4 * 2 wymaga reguły pierwszeństwa lub nawiasów, aby określić, które działanie wykonać jako pierwsze. W odwrotnej notacji polskiej operator zawsze działa na dwóch wartościach bezpośrednio przed nim, więc kolejność tokenów mówi wszystko: 3 4 2 * + daje 11, a 3 4 + 2 * daje 14. Dlatego do obliczenia wyrażenia wystarczy jeden stos i nie trzeba nigdy zaglądać naprzód.

Jak dzielić w Pythonie z zaokrąglaniem w kierunku zera?

Użyj int(a / b). Operator // zaokrągla w dół, więc -7 // 2 daje -4, a int(-7 / 2) daje -3. Dzielenie zmiennoprzecinkowe jest tutaj wystarczająco dokładne, ponieważ wartości mieszczą się w 32 bitach. W przypadku dowolnie dużych liczb całkowitych podziel wartości bezwzględne za pomocą //, a następnie przywróć znak.

Jak przekształcić zwykłe wyrażenie na odwrotną notację polską?

Algorytm stacji rozrządowej wykonuje to w jednym przebiegu, używając stosu operatorów. Liczby trafiają bezpośrednio na wyjście. Zanim operator zostanie umieszczony na stosie, każdy operator na stosie o wyższym lub równym priorytecie jest przenoszony na wyjście; nawias otwierający jest umieszczany na stosie, a nawias zamykający przenosi operatory na wyjście, aż napotka swój odpowiednik. Na końcu pozostałe operatory trafiają na wyjście.

Python

def evalRPN(tokens):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

tokens = ["8", "3", "-", "4", "*"]

Oczekiwane