Qual è il modo più veloce per verificare se Input String è un'espressione RPN corretta?

Question

Mi sono imbattuto in un'attività che consente di verificare se una stringa passata come argomento al metodo/funzione è un'istruzione corretta nel senso di notazione polacca inversa. Può contenere lettere dell'alfabeto minuscolo, segni di operazione e numeri interi. C'è un modo più veloce per controllarlo che leggere ogni personaggio separatamente e in realtà cercare di valutare l'intera espressione?

Answer 1

Non è necessario valutare l'intera espressione ma è necessario suddividerla in token e occorre conoscere la valenza di ogni operatore (ovvero, quanti operandi richiede). Per semplicità, lascia che la valenza di un operando sia 0; quindi effettuare le seguenti operazioni:

Set stack_size to 0; 
For Each token In expression: 
    Set stack_size to stack_size + 1 - valence(token) 
    If stack_size <= 0: Report failure 
If stack_size == 1: Report success 
Else    : Report failure 

Esempi utilizzando _ per meno unario.

expression:  3 4 + 1 * _ 
stack_size: 0 1 2 1 2 1 1 -> success 

expression:  2 3 4 + 1 * _ 
stack_size: 0 1 2 3 2 3 2 2 -> failure (not 1 at the end) 

expression:  2 3 + + 1 * _ 
stack_size: 0 1 2 1 0  -> failure (stack_size <= 0) 

Answer 2

È possibile utilizzare una tabella di analisi per riconoscere la notazione del lucido inverso. Richiede l'osservazione di ogni personaggio, ma è veloce.

Answer 3

Wikipedia ha un buon algoritmo per analizzare l'espressione. A meno che l'espressione non sia valida (nel qual caso è possibile terminare anticipatamente), non è possibile fare meglio di O (n). Cioè, devi valutare tutti i token nella stringa per assicurarti che sia valido.