Jaki jest najszybszy sposób sprawdzenia, czy wejściowy ciąg znaków jest prawidłowym wyrażeniem RPN?

Question

Natknąłem się na zadanie, które sprawia, że ​​sprawdzasz, czy String przekazany jako argument do twojej metody/funkcji jest poprawnym stwierdzeniem w sensie odwróconej polskiej notacji. Może zawierać małe litery alfabetu, znaki operacyjne i liczby całkowite. Czy jest jakiś szybszy sposób na sprawdzenie, niż czytanie każdej postaci osobno i próba oceny całego wyrażenia?

Answer 1

Nie musisz oceniać całego wyrażenia, ale musisz podzielić je na tokeny i musisz znać wartość każdego operatora (czyli ile operandów to wymaga). Dla uproszczenia niech wartość operandu będzie równa 0; następnie wykonaj następujące czynności:

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 

Przykłady przy użyciu _ dla jednolity minus.

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

Możesz użyć tabeli analizowania do rozpoznawania odwróconej notacji. Wymaga spojrzenia na każdą postać, ale jest szybki.

Answer 3

Wikipedia ma dobry algorytm do analizowania wyrażenia. O ile wyrażenie nie jest nieprawidłowe (w takim przypadku możesz wypowiedzieć się wcześniej), nie ma możliwości, byś mógł zrobić to lepiej niż O (n). Oznacza to, że musisz przetestować wszystkie tokeny w ciągu znaków, aby upewnić się, że są poprawne.