aby uzyskać równoważność obu stron?
Jeżeli chodzi o przejście postaci infiksowej w pre/post-fiksową to nie mam z tym problemu.
W drugą stronę pojawia się jednak mały problem.
Ostatnio zmieniony 14 kwie 2011, o 22:04 przez Afish, łącznie zmieniany 1 raz.
Powód:Poprawa wiadomości.
Nie do końca rozumiem, o co chodzi. Chcesz obliczyć to wyrażenie czy przekształcić do innej postaci?
Tu masz notację prefiksową. Algorytm postępowania przy obliczaniu tego wyrażenia jest bardzo prosty:
1.) Jeśli wyrażenie jest już puste, to zdejmij wynik ze stosu; jeśli nie to przejdź do 2
2.) Weź kolejny symbol wyrażenia
3.) Jeśli znak jest operatorem, odłóż na stos i przejdź do 2
4.) Jeśli znak jest liczbą, a na wierzchu stosu jest operator, odłóż na stos i przejdź do 2
5.) Jeśli znak jest liczbą (b), a na wierzchu stosu jest również liczba, to zdejmij ze stosu symbol (a), zdejmij ze stosu symbol (operator), wykonaj działanie a operator b, wynik odłóż na stos i przejdź do 1
Jeśli na którymś etapie okaże się, że danego kroku nie da się wykonać, to oznacza to, że wyrażenie nie było poprawnym wyrażeniem w postaci prefiksowej.
Algorytm jest dość intuicyjny: dopóki napotykamy operatory, odkładamy na stos; jak się zorientujemy, że mamy dostępne dwie liczby (jedną na stosie, drugą z obliczanego wyrażenia), to oznacza, że pod tą na stosie jest operator i możemy wykonać działanie. Wynik odkładamy na stos do dalszych obliczeń.
Jeśli chodzi natomiast o konwersję między tymi wyrażeniami, to algorytm jest oczywiście identyczny (jak znajdziesz te dwie liczby i operator, np. 2+2, to zamiast odkładania na stos liczby 4, odłóż na stos wyrażenie (2+2) ).
Jeśli chcesz dokonywać konwersji pomiędzy wyrażeniami w różnej postaci, to najwygodniej przedstawiać obliczenie w postaci drzewka obliczeniowego (liczby są liśćmi, operatory węzłami wewnętrznymi), np.:
Uploaded with
oznacza działanie \(\displaystyle{ 2 \cdot (3+5)}\). Wtedy wypisywanie węzłów drzewa jako operacja wykonana w przeszukaniu drzewa inorder zwróci wyrażenie w notacji infiksowej, w przeszukaniu preorder - prefiksowej, a postorder - postfiksowej.