Evaluate Reverse Polish Notation

Q: Qual è la complessità temporale della valutazione della notazione polacca inversa?

La soluzione con stack richiede un tempo O(n) per n token: ogni numero viene inserito una volta nello stack e ogni operatore esegue due estrazioni e un inserimento. Lo stack può contenere fino a circa n/2 valori, quindi lo spazio richiesto è O(n) . Ridurre ripetutamente il primo operatore richiede un tempo O(n²) , perché a ogni iterazione si ricomincia la ricerca dall'inizio.

Q: Perché la notazione polacca inversa non ha bisogno di parentesi?

Nella notazione ordinaria, 3 + 4 * 2 ha bisogno di una regola di precedenza o di parentesi per indicare quale operazione viene prima. Nella notazione polacca inversa, un operatore si applica sempre ai due valori che lo precedono immediatamente, quindi l’ordine dei token dice tutto: 3 4 2 * + è 11 e 3 4 + 2 * è 14. Ecco perché un’unica pila può valutarla senza mai dover guardare avanti.

Q: Come si esegue una divisione con troncamento verso zero in Python?

Usa int(a / b) . L'operatore // arrotonda per difetto, quindi -7 // 2 è -4, mentre int(-7 / 2) è -3. Qui la divisione in virgola mobile è sufficientemente precisa perché i valori rientrano in 32 bit. Per interi arbitrariamente grandi, dividi i valori assoluti con // e ripristina il segno in seguito.

MedioStack

+10

Ricevi un'espressione aritmetica in notazione polacca inversa, sotto forma di array di token. In questa notazione ogni operatore segue immediatamente i suoi due operandi, quindi 3 4 + significa 3 + 4 e 3 4 + 2 * significa (3 + 4) * 2, senza bisogno di parentesi. Ogni token è un intero o uno degli operatori +, -, * e /.

Valuta l'espressione e restituiscine il valore. La divisione conserva solo la parte intera e tronca verso zero: 7 / 2 è 3 e -7 / 2 è -3.

Funzione

evalRPN(tokens: string-array) → integer

tokensstring-array: i numeri e gli operatori dell’espressione, in ordine
Restituisceinteger: il valore dell'espressione

Vincoli

1 ≤ tokens.length ≤ 10⁴
Ogni token è +, -, *, / oppure un numero intero compreso tra -200 e 200, scritto in notazione decimale, con un segno meno iniziale se è negativo.
tokens è un'espressione valida in notazione polacca inversa.
Nessuna divisione per zero si verifica e ogni valore intermedio e finale è maggiore di -2³¹ e minore di 2³¹.

Esempi

Input: tokens = ["8", "3", "-", "4", "*"]
Output: 20
Spiegazione: - si applica ai due numeri che lo precedono nel loro ordine, 8 e poi 3, quindi dà 5, non -5. Poi * moltiplica quel 5 per 4, dando 20.

Input: tokens = ["6", "2", "9", "3", "/", "-", "*"]
Output: -6
Spiegazione: Il primo operatore, /, usa i due valori più recenti: 9 diviso 3 fa 3. Poi - calcola 2 meno quel 3, che fa -1, e * moltiplica 6 per -1.

Input: tokens = ["10", "-7", "2", "/", "+"]
Output: 7
Spiegazione: Il token -7 è un numero, non un operatore. -7 diviso 2 è -3.5, che viene troncato verso zero a -3 anziché arrotondato per difetto a -4, e 10 più -3 fa 7.

+18 test nascosti all’invio

Per approfondire

Riesci a ricostruire l’espressione nella notazione ordinaria, come (3 + 4) * 2, aggiungendo parentesi solo dove cambiano il significato?

Soluzione

La notazione polacca inversa non ha bisogno di parentesi perché l’ordine dei gettoni determina già l’ordine delle operazioni: ogni operatore si applica ai due valori immediatamente precedenti, e ciascuno di questi valori può essere il risultato di un operatore precedente. Una pila di valori valuta l’intera espressione in un unico passaggio da sinistra a destra. Le insidie sono nei dettagli: l’ordine degli operandi per - e /, distinguere l’operatore - dal numero -7 e la divisione che tronca verso zero.

Comprimi il primo operatore, ripeti

Corretto, ma non termina sui test più grandi

Intuizione

Ecco come risolveresti il problema su carta. Trova l'operatore più a sinistra. Prima di esso non c'è nessun operatore, quindi i due token immediatamente precedenti sono numeri semplici e sono i suoi operandi. Calcola il risultato e sostituisci quei tre token con un numero. L'espressione è ora più corta e significa ancora la stessa cosa. Ripeti finché non rimane un solo numero.

Prendi ["6", "2", "9", "3", "/", "-", "*"]. Il primo operatore è /, quindi 9 3 / diventa 3: ["6", "2", "3", "-", "*"]. Poi 2 3 - diventa -1: ["6", "-1", "*"]. Poi 6 -1 * diventa -6, la risposta.

È corretto perché ogni iterazione sostituisce una parte completa a b op con il suo valore, e gli operatori successivi trovano quel valore esattamente dove si trovava la parte. È lento perché a ogni iterazione si ricomincia la ricerca dall'inizio e poi si chiude un vuoto in mezzo all'array. Con 5.000 numeri seguiti da 4.999 operatori, il primo operatore si trova circa a metà per tutte le 4.999 iterazioni, quindi le sole ricerche esaminano circa 1.25 × 10^7 token. I numeri a sinistra dell'operatore cambiano appena da un'iterazione all'altra, eppure ogni iterazione li legge di nuovo.

Algoritmo

Copia i token in una lista che puoi modificare.
Scansiona dall'inizio fino al primo operatore, in posizione k.
Applicalo ai numeri nelle posizioni k-2 (a sinistra) e k-1 (a destra).
Sostituisci i tre token nelle posizioni k-2, k-1 e k con il risultato.
Ripeti finché non resta un solo token e restituiscilo come numero.

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

Un passaggio con una pila di valori

Intuizione

L'approccio con il collasso continua a rileggere i numeri a sinistra dell'operatore. Mettili invece su uno stack. Leggi i token una sola volta, da sinistra a destra. Un numero viene inserito nello stack. Un operatore rimuove dallo stack i due valori in cima, li combina e inserisce di nuovo il risultato, dove attende l'operatore successivo come qualsiasi altro valore.

Segui passo passo ["6", "2", "9", "3", "/", "-", "*"]. I quattro numeri vengono inseriti nello stack: [6, 2, 9, 3]. / estrae 3 e poi 9 e inserisce 9 / 3 = 3: [6, 2, 3]. - estrae 3 e poi 2 e inserisce 2 - 3 = -1: [6, -1]. * estrae -1 e poi 6 e inserisce 6 * -1 = -6. Rimane un valore, che è la risposta.

Perché funziona: in ogni momento lo stack contiene, nell'ordine, i valori dei pezzi completi letti fino a quel momento, e un operatore viene sempre applicato agli ultimi due. La cima dello stack è l'operando destro, perché è stato prodotto per ultimo, quindi va estratto per primo. Sbagliare quest'ordine si nota solo con - e /, dove 8 3 - deve dare 5 e non -5.

La divisione richiede attenzione in alcuni linguaggi. L'espressione tronca verso zero, ma // di Python, / di Ruby e %/% di R arrotondano per difetto, trasformando -3.5 in -4. Ogni numero viene inserito una volta e ogni operatore estrae due valori e ne inserisce uno, quindi il passaggio richiede O(n) tempo e lo stack non contiene mai più di n valori.

Algoritmo

Inizia con uno stack vuoto.
Per ogni token che è un numero, inserisci il suo valore.
Per ogni operatore, estrai l’operando destro, poi quello sinistro.
Calcola left op right, troncando verso zero per /, e inserisci il risultato.
Dopo l’ultimo token, restituisci l’unico valore sullo stack.

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]

Trappole e casi limite

Il ciclo dello stack è breve; la maggior parte delle risposte sbagliate dipende dall’ordine degli operandi e da come il linguaggio esegue la divisione.

Scambiare gli operandi. Il primo elemento estratto è l’operando destro: ["3", "5", "-"] dà -2 e ["2", "9", "/"] dà 0, non 4.
Riconoscere gli operatori dal loro primo carattere. -7 inizia con un segno meno, ma è un numero. Confronta l’intero token oppure controlla che sia lungo un solo carattere.
Arrotondare per difetto invece di troncare. -7 / 2 deve dare -3 e -1 / 3 deve dare 0. // di Python, / di Ruby, %/% di R e math.floor di Lua danno -4 e -1.
Stampare -0. In JavaScript e Lua tutti i numeri sono float, quindi 0 * -5 e Math.trunc(-1 / 3) danno zero negativo, che viene stampato come -0. Aggiungi 0 al valore finale per trasformarlo in 0.
Leggere un numero una cifra alla volta. Token come 13 e -200 hanno diversi caratteri; analizza l’intero token.
Presumere che l’ultimo token sia un operatore. Un singolo numero, come ["7"], è un’espressione valida il cui valore è 7.

Domande frequenti4

Qual è la complessità temporale della valutazione della notazione polacca inversa?

La soluzione con stack richiede un tempo O(n) per n token: ogni numero viene inserito una volta nello stack e ogni operatore esegue due estrazioni e un inserimento. Lo stack può contenere fino a circa n/2 valori, quindi lo spazio richiesto è O(n). Ridurre ripetutamente il primo operatore richiede un tempo O(n²), perché a ogni iterazione si ricomincia la ricerca dall'inizio.

Perché la notazione polacca inversa non ha bisogno di parentesi?

Nella notazione ordinaria, 3 + 4 * 2 ha bisogno di una regola di precedenza o di parentesi per indicare quale operazione viene prima. Nella notazione polacca inversa, un operatore si applica sempre ai due valori che lo precedono immediatamente, quindi l’ordine dei token dice tutto: 3 4 2 * + è 11 e 3 4 + 2 * è 14. Ecco perché un’unica pila può valutarla senza mai dover guardare avanti.

Come si esegue una divisione con troncamento verso zero in Python?

Usa int(a / b). L'operatore // arrotonda per difetto, quindi -7 // 2 è -4, mentre int(-7 / 2) è -3. Qui la divisione in virgola mobile è sufficientemente precisa perché i valori rientrano in 32 bit. Per interi arbitrariamente grandi, dividi i valori assoluti con // e ripristina il segno in seguito.

Come si trasforma un’espressione ordinaria in notazione polacca inversa?

L'algoritmo shunting-yard lo fa in un unico passaggio con una pila di operatori. I numeri vanno direttamente all'output. Prima di inserire un operatore nella pila, tutti gli operatori presenti nella pila con precedenza maggiore o uguale vengono spostati nell'output; una parentesi aperta viene inserita nella pila e una parentesi chiusa sposta gli operatori nell'output finché non incontra la parentesi corrispondente. Alla fine, gli operatori rimanenti vengono spostati nell'output.

Python

def evalRPN(tokens):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso