Evaluate Reverse Polish Notation

Q: Wie hoch ist die Zeitkomplexität der Auswertung der umgekehrten polnischen Notation?

Die Stapellösung benötigt für n Token eine Laufzeit von O(n) : Jede Zahl wird einmal auf den Stapel gelegt, und jeder Operator führt zwei Entnahmen und ein Auflegen aus. Der Stapel kann bis zu etwa n/2 Werte enthalten, daher beträgt der Speicherbedarf O(n) . Das wiederholte Zusammenfassen des jeweils ersten Operators benötigt O(n²) Zeit, da in jeder Runde erneut von Anfang an gesucht wird.

Q: Warum benötigt die umgekehrte polnische Notation keine Klammern?

In der üblichen Schreibweise braucht 3 + 4 * 2 eine Vorrangregel oder Klammern, um festzulegen, welche Operation zuerst ausgeführt wird. In der umgekehrten polnischen Notation wird ein Operator immer auf die beiden unmittelbar vor ihm stehenden Werte angewendet, sodass die Reihenfolge der Tokens alles aussagt: 3 4 2 * + ergibt 11 und 3 4 + 2 * ergibt 14. Deshalb kann ein einzelner Stack den Ausdruck auswerten, ohne jemals vorauszuschauen.

Q: Wie dividiert man in Python mit Abschneiden in Richtung null?

Verwende int(a / b) . Der Operator // rundet ab, daher ist -7 // 2 gleich -4, während int(-7 / 2) gleich -3 ist. Die Gleitkommadivision ist hier genau genug, weil die Werte in 32 Bit passen. Bei beliebig großen Ganzzahlen dividierst du die Absolutwerte mit // und fügst anschließend das Vorzeichen wieder hinzu.

MittelStack

+10

Du erhältst einen arithmetischen Ausdruck in umgekehrter polnischer Notation als Array von Token. In dieser Notation steht jeder Operator direkt hinter seinen beiden Operanden, sodass 3 4 + 3 + 4 bedeutet und 3 4 + 2 * (3 + 4) * 2 bedeutet, ohne dass Klammern erforderlich sind. Jedes Token ist eine ganze Zahl oder einer der Operatoren +, -, * und /.

Werte den Ausdruck aus und gib seinen Wert zurück. Bei der Division bleibt nur der ganzzahlige Anteil erhalten, und es wird gegen null abgeschnitten: 7 / 2 ist 3 und -7 / 2 ist -3.

Funktion

evalRPN(tokens: string-array) → integer

tokensstring-array: die Zahlen und Operatoren des Ausdrucks, der Reihe nach
Gibt zurückinteger: der Wert des Ausdrucks

Einschränkungen

1 ≤ tokens.length ≤ 10⁴
Jedes Token ist +, -, *, / oder eine ganze Zahl von -200 bis 200, die in Dezimalschreibweise geschrieben ist und bei negativen Zahlen ein vorangestelltes Minuszeichen hat.
tokens ist ein gültiger Ausdruck in umgekehrter polnischer Notation.
Es kommt zu keiner Division durch null, und jeder Zwischen- und Endwert ist größer als -2³¹ und kleiner als 2³¹.

Beispiele

Eingabe: tokens = ["8", "3", "-", "4", "*"]
Ausgabe: 20
Erklärung: Das - wird der Reihenfolge nach auf die beiden Zahlen davor angewendet, zuerst 8, dann 3, also ergibt es 5 und nicht -5. Dann multipliziert * diese 5 mit 4, was 20 ergibt.

Eingabe: tokens = ["6", "2", "9", "3", "/", "-", "*"]
Ausgabe: -6
Erklärung: Der erste Operator, /, verwendet die beiden zuletzt hinzugefügten Werte: 9 geteilt durch 3 ergibt 3. Dann berechnet - 2 minus diese 3, was -1 ergibt, und * multipliziert 6 mit -1.

Eingabe: tokens = ["10", "-7", "2", "/", "+"]
Ausgabe: 7
Erklärung: Das Token -7 ist eine Zahl, kein Operator. -7 geteilt durch 2 ergibt -3.5, was in Richtung null zu -3 abgeschnitten wird, statt auf -4 abgerundet zu werden, und 10 plus -3 ergibt 7.

+18 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du den Ausdruck in gewöhnlicher Schreibweise rekonstruieren, etwa (3 + 4) * 2, und dabei nur dort Klammern hinzufügen, wo sie die Bedeutung verändern?

Lösung

Die umgekehrte polnische Notation benötigt keine Klammern, weil die Reihenfolge der Tokens bereits die Reihenfolge der Berechnungen festlegt: Jeder Operator wird auf die beiden unmittelbar davor stehenden Werte angewendet, und jeder dieser Werte kann das Ergebnis eines früheren Operators sein. Ein Wertestapel wertet den gesamten Ausdruck in einem einzigen Durchlauf von links nach rechts aus. Die Fallstricke liegen im Detail: die Reihenfolge der Operanden bei - und /, die Unterscheidung des Operators - von der Zahl -7 und die Division, die gegen null abrundet.

Klappe den ersten Operator ein und wiederhole den Vorgang.

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

So würdest du es auf Papier ausrechnen. Finde den Operator ganz links. Vor ihm steht kein Operator, daher sind die beiden Tokens direkt davor einfache Zahlen und seine Operanden. Berechne das Ergebnis und ersetze diese drei Tokens durch eine Zahl. Der Ausdruck ist nun kürzer und bedeutet immer noch dasselbe. Wiederhole den Vorgang, bis nur noch eine Zahl übrig ist.

Nimm ["6", "2", "9", "3", "/", "-", "*"]. Der erste Operator ist /, also wird 9 3 / zu 3: ["6", "2", "3", "-", "*"]. Dann wird 2 3 - zu -1: ["6", "-1", "*"]. Dann wird 6 -1 * zu -6, der Antwort.

Das ist korrekt, weil in jeder Runde ein vollständiger Teil a b op durch seinen Wert ersetzt wird und die Operatoren danach diesen Wert genau an der Stelle sehen, an der der Teil stand. Es ist langsam, weil in jeder Runde erneut vom Anfang an gesucht und dann eine Lücke in der Mitte des Arrays geschlossen wird. Bei 5.000 Zahlen, auf die 4.999 Operatoren folgen, befindet sich der erste Operator bei allen 4.999 Runden ungefähr in der Mitte, sodass allein die Suchvorgänge etwa 1.25 × 10^7 Tokens prüfen. Die Zahlen links vom Operator ändern sich von einer Runde zur nächsten kaum, und trotzdem werden sie in jeder Runde erneut gelesen.

Algorithmus

Kopiere die Tokens in eine Liste, die du verändern kannst.
Durchsuche die Liste vom Anfang an bis zum ersten Operator an Position k.
Wende ihn auf die Zahlen an den Positionen k-2 (links) und k-1 (rechts) an.
Ersetze die drei Tokens an den Positionen k-2, k-1 und k durch das Ergebnis.
Wiederhole den Vorgang, bis ein Token übrig ist, und gib es als Zahl zurück.

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])

Ein Durchlauf mit einem Stapel von Werten

Idee

Beim Reduktionsansatz werden die Zahlen links vom Operator immer wieder gelesen. Lege sie stattdessen auf einen Stack. Lies die Tokens einmal von links nach rechts. Eine Zahl kommt auf den Stack. Ein Operator nimmt die beiden obersten Werte vom Stack, kombiniert sie und legt das Ergebnis zurück, wo es wie jeder andere Wert auf den nächsten Operator wartet.

Gehe ["6", "2", "9", "3", "/", "-", "*"] Schritt für Schritt durch. Die vier Zahlen kommen auf den Stack: [6, 2, 9, 3]. Der / nimmt 3 und dann 9 vom Stack und legt 9 / 3 = 3 darauf: [6, 2, 3]. Der - nimmt 3 und dann 2 vom Stack und legt 2 - 3 = -1 darauf: [6, -1]. Der * nimmt -1 und dann 6 vom Stack und legt 6 * -1 = -6 darauf. Ein Wert bleibt übrig, und das ist die Antwort.

Warum es funktioniert: Der Stack enthält jederzeit die Werte der bisher gelesenen vollständigen Teilausdrücke in ihrer Reihenfolge, und ein Operator wird immer auf die letzten beiden davon angewendet. Die Spitze des Stacks ist der rechte Operand, weil er zuletzt erzeugt wurde, also nimm ihn zuerst vom Stack. Eine falsche Reihenfolge fällt nur bei - und / auf, wo 8 3 - 5 und nicht -5 ergeben muss.

Bei der Division ist in manchen Sprachen Vorsicht geboten. Der Ausdruck rundet in Richtung null ab, aber Pythons //, Rubys / und Rs %/% runden ab, wodurch aus -3.5 -4 wird. Jede Zahl wird einmal auf den Stack gelegt, und jeder Operator nimmt zwei Werte vom Stack und legt einen darauf. Daher benötigt dieser Durchlauf O(n) Zeit, und der Stack enthält nie mehr als n Werte.

Algorithmus

Beginne mit einem leeren Stapel.
Schiebe für jedes Token, das eine Zahl ist, seinen Wert auf den Stapel.
Entferne für jeden Operator zuerst den rechten Operanden und dann den linken Operanden vom Stapel.
Berechne left op right, wobei bei / in Richtung null abgeschnitten wird, und schiebe das Ergebnis auf den Stapel.
Gib nach dem letzten Token den einzelnen Wert auf dem Stapel zurück.

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]

Stolperfallen und Grenzfälle

Die Stapelschleife ist kurz; die meisten falschen Antworten entstehen durch die Reihenfolge der Operanden und dadurch, wie eine Sprache dividiert.

Die Operanden vertauschen. Das erste Element, das entnommen wird, ist der rechte Operand: ["3", "5", "-"] ergibt -2 und ["2", "9", "/"] ergibt 0, nicht 4.
Operatoren anhand ihres ersten Zeichens erkennen. -7 beginnt mit einem Minuszeichen, ist aber eine Zahl. Vergleiche das ganze Token oder prüfe, ob es ein Zeichen lang ist.
Abrunden statt abschneiden. -7 / 2 muss -3 ergeben und -1 / 3 muss 0 ergeben. Python's //, Ruby's /, R's %/% und Lua's math.floor ergeben -4 und -1.
-0 ausgeben. In JavaScript und Lua ist jede Zahl ein Gleitkommawert, deshalb ergeben 0 * -5 und Math.trunc(-1 / 3) negative null, die als -0 ausgegeben wird. Addiere 0 zum Endwert, um daraus 0 zu machen.
Eine Zahl Ziffer für Ziffer einlesen. Tokens wie 13 und -200 haben mehrere Zeichen; parse das ganze Token.
Annehmen, dass das letzte Token ein Operator ist. Eine einzelne Zahl wie ["7"] ist ein gültiger Ausdruck, dessen Wert 7 ist.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität der Auswertung der umgekehrten polnischen Notation?

Die Stapellösung benötigt für n Token eine Laufzeit von O(n): Jede Zahl wird einmal auf den Stapel gelegt, und jeder Operator führt zwei Entnahmen und ein Auflegen aus. Der Stapel kann bis zu etwa n/2 Werte enthalten, daher beträgt der Speicherbedarf O(n). Das wiederholte Zusammenfassen des jeweils ersten Operators benötigt O(n²) Zeit, da in jeder Runde erneut von Anfang an gesucht wird.

Warum benötigt die umgekehrte polnische Notation keine Klammern?

In der üblichen Schreibweise braucht 3 + 4 * 2 eine Vorrangregel oder Klammern, um festzulegen, welche Operation zuerst ausgeführt wird. In der umgekehrten polnischen Notation wird ein Operator immer auf die beiden unmittelbar vor ihm stehenden Werte angewendet, sodass die Reihenfolge der Tokens alles aussagt: 3 4 2 * + ergibt 11 und 3 4 + 2 * ergibt 14. Deshalb kann ein einzelner Stack den Ausdruck auswerten, ohne jemals vorauszuschauen.

Wie dividiert man in Python mit Abschneiden in Richtung null?

Verwende int(a / b). Der Operator // rundet ab, daher ist -7 // 2 gleich -4, während int(-7 / 2) gleich -3 ist. Die Gleitkommadivision ist hier genau genug, weil die Werte in 32 Bit passen. Bei beliebig großen Ganzzahlen dividierst du die Absolutwerte mit // und fügst anschließend das Vorzeichen wieder hinzu.

Wie wandelt man einen gewöhnlichen Ausdruck in die umgekehrte polnische Notation um?

Der Shunting-Yard-Algorithmus erledigt das in einem Durchlauf mit einem Stapel von Operatoren. Zahlen gelangen direkt in die Ausgabe. Bevor ein Operator auf den Stapel gelegt wird, wird jeder Operator auf dem Stapel mit höherer oder gleicher Priorität in die Ausgabe verschoben; eine öffnende Klammer wird auf den Stapel gelegt, und eine schließende Klammer verschiebt Operatoren in die Ausgabe, bis sie auf ihr Gegenstück trifft. Am Ende gelangen die verbleibenden Operatoren in die Ausgabe.

Python

def evalRPN(tokens):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet