InfixToPostfix

[Nils_13]

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 ?

[Nils_13]

:wall: Ich such mich hier blutig und eben habe ich alles nochmal komplett überdacht. Was fällt mir dann auf ?

Delphi-Quellcode:

while Tokens[i].Wertigkeit < Stack.Peek.Wertigkeit do

ist falsch, es muss

Delphi-Quellcode:

while Tokens[i].Wertigkeit <= Stack.Peek.Wertigkeit do

heißen.

[WS1976]

Hallo Nils,

Nimm die Quasilinearpotenz deines Code und potenziere sie mit der reduziblen russischen
Potenz der Rutschwurzel!
(War ein kleiner Spass aber so komm ich mir vor wenn ich deinen Beitrag lese)

was ist ein Infix, was ein Postfix?
was ist TTokenstack? Wo hast du das her?


Sorry meine dummen Fragen aber du musst dich nicht wundern wenn du keine Anwort bekommst!
Grüsse
Rainer

[ghost007]

Infix und Postfix sind Schreibweisen für Funktionen und deren Parameter.

Infix: Der Operator ist umgeben von den Parametern, er ist "innen"
Bsp: a + b
Die Funktion ist: +
Die Parameter: a,b

Postfix: Der Operator steht hinter seinen Parametern, post -> dt. nach
Bsp: a b *
Die Funktion ist: *
Die Parameter: a,b

MfG - Ghost007

[Edit] Die Angabe der Stackstruktur fehlt, wobei das eigentlich kein problem ist. Funktional ist es hier beschrieben.[/Edit]

[Edit2]@Topic: Hab grade leider keine Zeit um deinen Code durchzugehen, muss meinen Flieger erwischen. Aber schau ihn mir morgen gerne an. ;)[/Edit2]

[WS1976]

Hallo ghost007,

du kannst mir schon zugestehen, dass ich weiss was ein Stack ist.
(ich muss mir noch überlegen ob ich beleidigt sein soll wegen des Verweises auf Wikipedia).
Ich hätte aber trotzdem gerne gewusst wie der Stack realisiert ist.

Grüsse
Rainer

[worker]

Zitat:

Zitat von WS1976

Ich hätte aber trotzdem gerne gewusst wie der Stack realisiert ist.

Was gibt es da schon groß zu realisieren, außer die Implementierung von Pop und Push auf Basis einer Liste? :gruebel:

Zitat:

Zitat von WS1976

was ist ein Infix, was ein Postfix?
was ist TTokenstack? Wo hast du das her?

Desweiteren lassen Deine Fragen keine andere Vermutung zu, als die, dass Du ganz einfach keine Ahnung hast.
Woher soll ghost007 wissen, dass es nicht so ist?

Ihm damit zu 'drohen', dass Du evtl. beleidigt bist - unter aller Kanone.

Du bist hier im Forum halt nicht so populär wie manch anderer, bei dem man weiß, dass man ihm nicht mit Erläuterungen zu Grundlagen kommen muss.

[WS1976]

Hallo worker,

müssen solche Beiträge sein?
Kannst du dich bitte auf einem sachlichen Niveau bewegen!

Danke
Rainer

[worker]

Hallo.

[OT]

Zitat:

Zitat von WS1976

müssen solche Beiträge sein?

In Deinem Fall: Ja, müssen Sie. Erläuterung dazu per PM.

Zitat:

Zitat von WS1976

Kannst du dich bitte auf einem sachlichen Niveau bewegen!

Meine Beiträge sind stets sachlich.
[/OT]

[Nils_13]

Hört auf euch zu kloppen. Das Problem ist schon längst gelöst, wenn ihr weiter macht bitte ich darum, das Thema zu schließen. Außerdem ist es so spezifisch, dass eh wahrscheinlich keiner mehr hier was schreiben wird.