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 O(n) Zeit: Jede Zahl wird einmal auf den Stapel gelegt, und jeder Operator führt zwei Entnahmen und einen Stapelvorgang aus. Der Stapel enthält bis zu etwa n/2 Werte, daher beträgt der Speicherbedarf O(n) .

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

In der gewöhnlichen Schreibweise benötigt 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 Werte direkt vor ihm angewendet, daher entscheidet die Reihenfolge der Tokens: 3 4 2 * + ergibt 11 und 3 4 + 2 * ergibt 14.

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 Division mit Gleitkommazahlen ist für 32-Bit-Werte genau genug. Bei größeren Ganzzahlen dividiere die Absolutwerte mit // und setze das Vorzeichen wieder ein.

MittelStack

+10

Du erhältst einen arithmetischen Ausdruck in umgekehrter polnischer Notation als Array von Tokens. Jeder Operator steht direkt nach seinen beiden Operanden, daher bedeutet 3 4 + 3 + 4 und 3 4 + 2 * (3 + 4) * 2, ganz ohne Klammern. Jedes Token ist eine ganze Zahl oder einer der Operatoren +, -, * und /.

Gib den Wert des Ausdrucks zurück. Bei der Division 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 Reihenfolge 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 als Dezimalzahl mit einem vorangestellten Minuszeichen geschrieben wird, wenn sie negativ ist.
tokens ist ein gültiger Ausdruck in umgekehrter polnischer Notation.
Es tritt keine Division durch null auf, 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 auf 8 und dann auf 3 angewendet, in dieser Reihenfolge, und ergibt somit 5, nicht -5. Dann multipliziert * diese 5 mit 4, was 20 ergibt.

Eingabe: tokens = ["6", "2", "9", "3", "/", "-", "*"]
Ausgabe: -6
Erklärung: / verwendet die beiden zuletzt verwendeten Werte: 9 geteilt durch 3 ergibt 3. Dann berechnet - 2 minus 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 ist -3.5, was gegen null auf -3 abgeschnitten wird, nicht auf -4, und 10 plus -3 ist 7.

Weiterführende Frage

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

Lösung

Jeder Operator wird auf die beiden unmittelbar davorstehenden Werte angewendet, und einer davon kann das Ergebnis eines vorherigen Operators sein. So wertet ein Stapel von Werten den Ausdruck in einem Durchgang aus. Die Tücken sind die Reihenfolge der Operanden bei - und /, die Unterscheidung des Operators - von der Zahl -7 und die Ganzzahldivision.

Den ersten Operator zusammenfassen, wiederholen

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

Idee

Finde den am weitesten links stehenden Operator. Davor steht kein Operator, also sind die beiden Tokens davor Zahlen, seine Operanden. Ersetze diese drei Tokens durch ihr Ergebnis. Die Operatoren danach sehen diesen Wert an der Stelle, an der das Stück stand, sodass der Ausdruck seine Bedeutung behält. Wiederhole das, bis eine Zahl übrig ist.

Jede Runde beginnt die Suche erneut von vorn. Bei 5,000 Zahlen gefolgt von 4,999 Operatoren befindet sich der erste Operator in jeder Runde ungefähr in der Mitte, sodass allein die Suchvorgänge etwa 1.25 × 10^7 Tokens lesen.

Algorithmus

Kopiere die Tokens in eine Liste, die du ändern kannst.
Durchsuche die Liste vom Anfang bis zum ersten Operator an Position k.
Wende ihn auf die Zahlen bei k-2 (links) und k-1 (rechts) an.
Ersetze die drei Tokens bei k-2, k-1 und k durch das Ergebnis.
Wiederhole dies, 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

Lege die Werte links vom Operator auf einen Stack, statt sie erneut einzulesen. Eine Zahl kommt auf den Stack. Ein Operator nimmt zwei Werte vom Stack, kombiniert sie und legt das Ergebnis darauf, wo es wie jeder andere Wert auf den nächsten Operator wartet. Der Stack enthält immer der Reihe nach die Werte der vollständigen Teile, die bisher gelesen wurden, sodass ein Operator immer auf die beiden obersten Werte angewendet wird. Der oberste Wert ist der rechte Operand, weil er zuletzt erzeugt wurde.

Bei 6 2 9 3 / - * nimmt / zuerst 3, dann 9 vom Stack und legt 3 darauf, - nimmt zuerst 3, dann 2 vom Stack und legt -1 darauf, und * legt 6 × -1 = -6 darauf. Jedes Token wird einmal verarbeitet: O(n) Zeit und O(n) Speicherplatz.

Algorithmus

Beginne mit einem leeren Stapel.
Lege 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 / gegen null abgeschnitten wird, und lege 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 Operanden vertauschen. Das erste entnommene Element 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 daher das gesamte Token.
Abrunden statt Abschneiden. Pythons //, Rubys /, Rs %/% und Luas math.floor machen aus -7 / 2 den Wert -4 und aus -1 / 3 den Wert -1.
-0 ausgeben. In JavaScript und Lua ergeben 0 * -5 und Math.trunc(-1 / 3) negative Null. Addiere 0 zum Endwert.

Häufige Fragen4

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

Die Stapellösung benötigt für n Token O(n) Zeit: Jede Zahl wird einmal auf den Stapel gelegt, und jeder Operator führt zwei Entnahmen und einen Stapelvorgang aus. Der Stapel enthält bis zu etwa n/2 Werte, daher beträgt der Speicherbedarf O(n).

Warum benötigt die umgekehrte polnische Notation keine Klammern?

In der gewöhnlichen Schreibweise benötigt 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 Werte direkt vor ihm angewendet, daher entscheidet die Reihenfolge der Tokens: 3 4 2 * + ergibt 11 und 3 4 + 2 * ergibt 14.

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 Division mit Gleitkommazahlen ist für 32-Bit-Werte genau genug. Bei größeren Ganzzahlen dividiere die Absolutwerte mit // und setze das Vorzeichen wieder ein.

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

Der Shunting-Yard-Algorithmus erledigt das in einem Durchlauf mit einem Stapel von Operatoren. Zahlen gehen direkt in die Ausgabe. Bevor ein Operator auf den Stapel gelegt wird, werden alle Operatoren mit höherer oder gleicher Priorität vom Stapel in die Ausgabe verschoben. Eine schließende Klammer verschiebt Operatoren so lange aus dem Stapel, bis die zugehörige öffnende Klammer erreicht ist. Am Ende werden die übrigen Operatoren in die Ausgabe verschoben.

def evalRPN(tokens):
    # Schreibe hier Code

Test #1

Test #2

Test #3

Argument

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

Erwartete Ausgabe