Chciałem napisać własną implementację konwersji i interpretacji odwrotnej notacji polskiej.
Jednak algorytm konwersji z notacji infiksowej na postfiksową nie działa jak powinien.
Otóż przy próbie wykonania działania np "2 + 2 - 2" funkcja zwraca "2 2 + 2" zamiast "2 2 + 2 -".
Działanie "(2 + 2) - 2" oblicza się poprawnie. Czy to błędna implementacja czy algorytm sam w sobie jest wadliwy?
Bazowałem się na tym opisie:
http://pl.wikipedia.org/wiki/ONP#Algorytm_konwersji_z_notacji_infiksowej_do_ONP
Mój kod:
http://4programmers.net/Delphi/Gotowce/Funkcja_Eval_(interpreter_równań)
Fragment kodu o którym mowa (wewnątrz funckji InfixToPostfix):
for i := 0 to input.Count - 1 do begin
if IsNumber(input.Strings[i]) then // znaleziono liczbe
output.Push(input.Strings[i]) // dodanie jej na wyjscie
else if input.Strings[i] = '(' then // znaleziono lewy nawias
stack.Push(input.Strings[i]) // wrzucenie go na stos
else if input.Strings[i] = ')' then begin // znaleziono prawy nawias
repeat
tmp := stack.Pop; // pobranie ze stosu operatora
if tmp <> '(' then output.Push(tmp); // wrzucenie go na wyjscie
until tmp = '('; // dopoki znaleziono prawy nawias
end else begin // znaleziono operator
if stack.IsEmpty then // stos pusty
stack.Push(input.Strings[i]) // wrzuc na niego znaleziony operator
else begin // stos ma elementy
o1 := OperatorType(input.Strings[i][1]); // odczytanie wlasciwosci operatora
if o1.Priority = -1 then Break; // niepoprawny operator!
while not stack.IsEmpty do begin // powtarzaj dopoki stos ma elementy
tmp := stack.Pop; // pobranie operatora
o2 := OperatorType(tmp[1]); // odczytanie jego wlasciwosci
if ((not o1.AssociativeRight) and (o1.Priority <= o2.Priority)) or
(o1.AssociativeRight and (o1.Priority < o2.Priority)) then begin
output.Push(tmp); // operator ze stosu na wyjscie
end else begin
stack.Push(tmp);
stack.Push(input.Strings[i][1]);
Break;
end;
end;
end;
end;
end;
while not stack.IsEmpty do // wypisanie operatorow na wyjscie
output.Push(stack.Pop);