Evaluate Reverse Polish Notation
Otrzymujesz wyrażenie arytmetyczne zapisane w odwrotnej notacji polskiej jako tablicę tokenów. Każdy operator występuje bezpośrednio po swoich dwóch operandach, więc 3 4 + oznacza 3 + 4, a 3 4 + 2 * oznacza (3 + 4) * 2, bez nawiasów. Każdy token jest liczbą całkowitą lub jednym z operatorów +, -, * i /.
Zwróć wartość wyrażenia. Dzielenie zaokrągla wynik w kierunku zera: 7 / 2 to 3, a -7 / 2 to -3.
Funkcja
- tokensstring-array
- liczby i operatory wyrażenia, w kolejności
- Zwracainteger
- wartość wyrażenia
Ograniczenia
1 ≤ tokens.length ≤ 104- Każdy token to
+,-,*,/lub liczba całkowita z zakresu od-200do200, zapisana w systemie dziesiętnym, z poprzedzającym ją znakiem minus, jeśli jest ujemna. tokensjest 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ż
-231i mniejsza niż231.
Przykłady
- Wejście
- tokens = ["8", "3", "-", "4", "*"]
- Wyjście
- 20
- Wyjaśnienie
- Operator
-jest stosowany najpierw do 8, a potem do 3, w tej kolejności, 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
/używa dwóch najnowszych wartości: 9 podzielone przez 3 to 3. Następnie-oblicza 2 minus 3, co daje -1, a*mnoży 6 przez -1.
- Wejście
- tokens = ["10", "-7", "2", "/", "+"]
- Wyjście
- 7
- Wyjaśnienie
- Token
-7to liczba, a nie operator. -7 podzielone przez 2 to -3.5, co po obcięciu w kierunku zera daje -3, a nie -4, a 10 plus -3 to 7.
Pytanie dodatkowe
Czy potrafisz odtworzyć wyrażenie w zwykłym zapisie, na przykład (3 + 4) * 2, dodając nawiasy tylko tam, gdzie zmieniają znaczenie?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Odczytuj żetony od lewej do prawej. Gdy napotkasz operator, do których dwóch wartości się odnosi? Sprawdź kolejność, w jakiej te wartości zostały utworzone.
Operator zawsze działa na dwóch ostatnich wartościach, których nie użył jeszcze żaden operator, a jego wynik staje się nową wartością dla kolejnych operatorów. „Ostatnia, która nie została jeszcze użyta” to dokładnie to, co zapewnia stos.
Umieść każdą liczbę na stosie. Gdy napotkasz operator, zdejmij najpierw prawy operand, a potem lewy, połącz je w tej kolejności i umieść wynik na stosie. Gdy skończą się tokeny, na stosie pozostanie jedna wartość: odpowiedź. Upewnij się, że dzielenie zaokrągla wynik w kierunku zera.
Rozwiązanie
Każdy operator stosuje się do dwóch wartości bezpośrednio przed nim, a jedna z nich może być wynikiem wcześniejszego operatora. Dzięki temu stos wartości oblicza wyrażenie w jednym przebiegu. Pułapki to kolejność operandów dla - i /, odróżnianie operatora - od liczby -7 oraz dzielenie z obcięciem.
Zwiń pierwszy operator, powtórz
Poprawne, ale nie kończy się na największych testach
Intuicja
Znajdź operator najbardziej wysunięty w lewo. Nie ma przed nim żadnego operatora, więc dwa poprzedzające go tokeny to liczby, jego operandy. Zastąp te trzy tokeny ich wynikiem. Operatory znajdujące się za nim widzą tę wartość w miejscu, w którym znajdował się ten fragment, więc wyrażenie zachowuje swoje znaczenie. Powtarzaj, aż zostanie jedna liczba.
W każdej rundzie wyszukiwanie zaczyna się od początku. Przy 5,000 liczbach, po których następuje 4,999 operatorów, pierwszy operator znajduje się mniej więcej w połowie wyrażenia w każdej rundzie, więc samo wyszukiwanie odczytuje około 1.25 × 10^7 tokenów.
Algorytm
- Skopiuj tokeny do listy, którą możesz zmieniać.
- Skanuj od początku do pierwszego operatora, na pozycji
k. - Zastosuj go do liczb na pozycjach
k-2(po lewej) ik-1(po prawej). - Zastąp trzy tokeny na pozycjach
k-2,k-1ikwynikiem. - 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
Przechowuj wartości znajdujące się po lewej stronie operatora na stosie, zamiast odczytywać je ponownie. Liczba trafia na stos. Operator zdejmuje ze stosu dwie wartości, łączy je i umieszcza wynik na stosie, gdzie czeka na kolejny operator, tak jak każda inna wartość. Stos zawsze zawiera wartości dotychczas odczytanych kompletnych części, w odpowiedniej kolejności, więc operator zawsze działa na dwóch wartościach ze szczytu. Wartość na szczycie jest prawym operandem, ponieważ została utworzona jako ostatnia.
W 6 2 9 3 / - * operator / zdejmuje ze stosu najpierw 3, a potem 9 i umieszcza na stosie 3, operator - zdejmuje ze stosu 3, a potem 2 i umieszcza na stosie -1, a operator * umieszcza na stosie wynik 6 × -1 = -6. Każdy token jest obsługiwany raz: czas O(n) i pamięć O(n).
Algorytm
- Rozpocznij od pustego stosu.
- Dla każdego tokenu będącego liczbą umieść jego wartość na stosie.
- Dla każdego operatora zdejmij prawy operand, a następnie lewy operand.
- Oblicz
left op right, obcinając wynik dzielenia w kierunku zera dla/, 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
- Zamiana operandów. Pierwszy zdjęty element to prawy operand:
["3", "5", "-"]daje -2, a["2", "9", "/"]daje 0, a nie 4. - Rozpoznawanie operatorów po ich pierwszym znaku.
-7zaczyna się od znaku minus, ale jest liczbą, więc porównuj cały token. - Zaokrąglanie w dół zamiast obcinania.
//w Pythonie,/w Ruby,%/%w R imath.floorw Lua zamieniają-7 / 2na -4, a-1 / 3na -1. - Wyświetlanie
-0. W JavaScript i Lua0 * -5iMath.trunc(-1 / 3)dają ujemne zero. Dodaj 0 do końcowej wartości.
Najczęstsze pytania4
Jaka jest złożoność czasowa obliczania odwrotnej notacji polskiej?
Rozwiązanie ze stosem działa w czasie O(n) dla n tokenów: każda liczba jest odkładana na stos raz, a każdy operator wykonuje dwa zdjęcia ze stosu i jedno odłożenie. Stos przechowuje do około n/2 wartości, więc złożoność pamięciowa wynosi O(n).
Dlaczego odwrotna notacja polska nie wymaga nawiasów?
W zwykłym zapisie 3 + 4 * 2 potrzebna jest reguła pierwszeństwa lub nawiasy, aby określić, które działanie wykonuje się jako pierwsze. W odwrotnej notacji polskiej operator zawsze działa na dwóch wartościach bezpośrednio przed nim, więc o wyniku decyduje kolejność tokenów: 3 4 2 * + to 11, a 3 4 + 2 * to 14.
Jak dzielić w Pythonie, zaokrąglając wynik 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 wystarczająco dokładne dla wartości 32-bitowych. W przypadku większych liczb całkowitych podziel wartości bezwzględne za pomocą // i przywróć znak.
Jak przekształcić zwykłe wyrażenie w 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. Przed umieszczeniem operatora na stosie przenieś na wyjście wszystkie znajdujące się na nim operatory o wyższym lub równym priorytecie. Nawias zamykający przenosi operatory ze stosu, aż do napotkania odpowiadającego mu nawiasu otwierającego. Na końcu pozostałe operatory trafiają na wyjście.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def evalRPN(tokens):
# Wpisz tutaj kodTest #1
Test #2
Test #3
Argument
tokens = ["8", "3", "-", "4", "*"]
Oczekiwany wynik
20