Hej, ma ktoś opis algorytmu ONP, ale taki który jako strukturę pomocniczą wykorzystuje drzewo ?
I czy jest to rozwiązanie optymalniejsze od tradycyjnego rozwiązania na stosie i kolejce ?
0
0
A na co komu drzewo w ONP?
0
Jako alternatywę do stosu i kolejki, chyba jasne to ?
Jako ONP rozumiem konwersję (z postaci) InFixowej i ewaluację z postaci PostFixowej (jeśli sie czepiasz słówek)
No chyba ze potrafisz zrobić ONP bez stosu, kolejki i drzewa ;D
0
Jak dla mnie to w algorytmach konwersji do ONP widać pewną analogię do DFSa. Stos w tych algorytmach jest tak samo długi jak np zagłębienie nawiasów, to samo byłoby przy DFSie. Te stosowe algorytmy operują na drzewie implicite, gdzie w pamięci przechowywana jest tylko jedna ścieżka.
Obydwa algorytmy z Wiki, czy to z explicite stosem, czy też z implicite stosem (tzn rekurencyjne), mają złożoność liniową i jak mniemam, niską stałą. Jeśli zastosujesz explicite drzewo to raczej stałej nie zbijesz. Co najwyżej możesz mieć satysfakcję, że skleciłeś własny algorytm.
0
No dzięki za odpowiedź.
Może ktoś zauważy topic i przeniesie do Algorytmów i struktur danych. Bo w tym gąszczu już jutro przestanie istniec :>