Hi,
ich schreibe gerade eine Funktion, die Infix zu Postfix konvertieren soll. Sie ist mittlerweile so weit, dass bei der Eingabe 3*(1+2)+(5/3)^2 das korrekte Ergebnis 3 1 2 + * 5 3 / 2 ^ + rauskommt. Allerdings ergibt 3*(1+2)+(5/3)^2+3 fälschlicherweise 3 1 2 + * 5 3 / 2 ^ 3 + +. Korrekt wäre 3 1 2 + * 5 3 / 2 ^ + 3 +. Der Algo ist eine Abwandlung des Shunting yard. Die Idee:
1. Alle Tokens durchgehen.
2. Ist das Token ein Operand, fügt man es dem Ergebnis hinzu.
3. Ist das Token ein Operator, popt man solange die Wertigkeit des Operators kleiner als die des Tokens am obersten Punkt des Stacks ist. Außerdem pusht man das Token in den Stack.
4. Ist das Token eine (, pusht man es in den Stack.
5. Ist das Token eine ), popt man und gibt aus, bis der oberste Punkt des Stacks kein ( mehr ist.
6. Den Stack leeren und an das Ergebnis hängen.
Delphi-Quellcode:
TToken = record
Inhalt : ShortString;
Wertigkeit : ShortInt;
end;
function InfixToPostfix(s : String) : TStrings;
var Tokens : TDynTokenArray;
i : Integer;
Stack : TTokenStack;
begin
Result := TStringList.Create;
Tokens := Tokenize(s);
Stack := TTokenStack.Create(Length(Tokens));
for i := 0 to High(Tokens) do
begin
if Tokens[i].Wertigkeit = 0 then // Zahlen
Result.Add(Tokens[i].Inhalt)
else if Tokens[i].Wertigkeit = -1 then // Klammer auf
Stack.Push(Tokens[i])
else if Tokens[i].Wertigkeit = -2 then // Klammer zu
begin
while Stack.Peek.Wertigkeit <> -1 do
Result.Add(Stack.Pop.Inhalt);
Stack.Pop;
end else
begin
// Operatoren
while (Tokens[i].Wertigkeit < Stack.Peek.Wertigkeit) do
Result.Add(Stack.Pop.Inhalt);
Stack.Push(Tokens[i]);
end;
end;
while Stack.Count > 0 do
Result.Add(Stack.Pop.Inhalt);
Stack.Free;
end;
Natürlich existiert noch ein Tokenizer. Ganz einfacher Code, da er eventuell nötig ist oder jemanden interessiert:
Delphi-Quellcode:
function Tokenize(s :
String) : TDynTokenArray;
function ScanNumber(s :
String; i : Integer) :
String;
var j : integer;
begin
j := i;
while (j < Length(s))
and (s[Succ(j)]
in ['
0'..'
9', '
.', '
,'])
do
inc(j);
Result := Copy(s, i, j-i+1);
end;
function ScanIdentifier(s :
String; i : Integer) :
String;
var j : integer;
begin
j := i;
while (j < Length(s))
and (s[Succ(j)]
in ['
a'..'
z', '
A'..'
Z'])
do
inc(j);
Result := Copy(s, i, j-i+1);
end;
var i : Integer;
Token : TToken;
begin
i := 1;
while i <= Length(s)
do
begin
with Token
do
begin
if s[i]
in ['
0'..'
9']
then
begin
Inhalt := ScanNumber(s, i);
Wertigkeit := 0;
end else
{ if s[i] in ['a'..'z', 'A'..'Z'] then
begin
Inhalt := ScanIdentifier(s, i);
Wertigkeit :=
end; }
if s[i]
in ['
^', '
%']
then
begin
Inhalt := s[i];
Wertigkeit := 9;
end else
if s[i]
in ['
*', '
/']
then
begin
Inhalt := s[i];
Wertigkeit := 8;
end else
if s[i]
in ['
+', '
-']
then
begin
Inhalt := s[i];
Wertigkeit := 6;
end else
if s[i] = '
('
then
begin
Inhalt := s[i];
Wertigkeit := -1;
end else
if s[i] = '
)'
then
begin
Inhalt := s[i];
Wertigkeit := -2;
end else
raise Exception.Create('
[TOKENIZER] Token "'+s[i]+'
" unbekannt. Abbruch.');
inc(i, Length(Inhalt));
end;
SetLength(Result, Succ(Length(Result)));
Result[High(Result)] := Token;
end;
end;
Seht ihr den Grund für den Fehler bei der einen Rechnung ?
Zitat
Baum-Darstellung
