Infix to Postfix

[ldn (Gast)]

Hallo Forum

ich muss einen infix-to-postfix-"Parser" programmieren.
mein jetztiger code funktioniert auch schon fast (die stack-funktionen 
hab ich jz mal weggelassen):

int priority(char c) {
  if (c == '/' || c == '*')
    return 2;
  if (c == '+' || c == '-')
    return 1;
  return 0;
}

void infix2postfix(char *buffer, const char *term) {
  char x;
  while (*term) {
    if (isalnum(*term))
      *buffer++ = *term;
      //printf("%c", *term);
    else if (*term == '(')
      push('(');
    else {
      if (*term == ')')
        while ((x = pop()) != '(') {
          *buffer++ = x;
          //printf("%c", x);
        }
      else {
        while (priority(*term) <= priority(top()) && !isEmpty()) {
          x = pop();
          *buffer++ = x;
          //printf("%c", x);
        }
        push(*term);
      }
    }
    term++;
  }
  while (!isEmpty()) {
    x = pop();
    *buffer++ = x;
    //printf("%c", x);
  }
  *buffer = '\0';
}

Es klappt eig ganz gut, nur:
Infix: (2+30)*4^25 <-- Eingabe
Postfix: 230+425^* <-- Ausgabe
Man sieht: die Zahlen werde nicht richtig getrennt. Ist ja uach klar, 
ich füge nirgends ein ' ' ein. Nur ich weiß jetzt nicht wie, oder eher 
wo, ich das Leerzeichen einfügen muss.

Wenn man den Code oben anders effektiver schreiben kann, gerne Tipps 
dazu.

Danke für euere Hilfe

[Karl H. (kbuchegg)]

ldn schrieb:

> Es klappt eig ganz gut, nur:
> Infix: (2+30)*4^25 <-- Eingabe
> Postfix: 230+425^* <-- Ausgabe
> Man sieht: die Zahlen werde nicht richtig getrennt. Ist ja uach klar,
> ich füge nirgends ein ' ' ein. Nur ich weiß jetzt nicht wie, oder eher
> wo, ich das Leerzeichen einfügen muss.

Das kannst du so auch nicht, denn du unterscheidest in deiner 
übergeordneten Schleife hier

  while (*term) {
    if (isalnum(*term))
      *buffer++ = *term;
...

nicht, ob damit eine Zahl komplett ist oder nicht, sondern du behandelst 
das alles, als ob immer nur 1 Zeichen relevant ist.
Mit anderen Worten: dein Parser kann nicht erkennen, dass eine 'Einheit' 
(Zahl, Variablennamen, Operator, ...) aus mehreren Zeichen bestehen 
könnte, sondern geht immer davon aus, dass es sich beim nächsten zu 
parsenden Symbol um genau 1 Zeichen handelt.

Deshalb agieren echte Parser auch nicht in dieser Form direkt auf dem 
Quelltext sondern benutzen einen sog. lexikalischen Parser, der ihnen 
das jeweils nächste Symbol zum Parsen heraus holt. So ein lexiaklischer 
Parser untersucht die jeweils nächsten Ccaracter aus der EIngabe und 
stellt zb fest, dass da jetzt 3 Ziffer-Character hintereinander kommen, 
die er zu einer Zahl zusammenfassen soll. Der Syntaxparser kriegt vom 
lexikalischen Parser dann die Information, dass als nächstes Symbol in 
der Eingabe eine Zahl vorhanden ist (deren Wert beispielsweise 385 
beträgt), oder das in der EIngabe als nächstes Symbol ein 'kleiner 
gleich' Symbol vorhanden ist.

D.h. für den Parser gestaltet sich die Extraktion des nächsten Symbols 
aus der Eingabe nicht mehr so einfach

  while (*term) {

dadurch, dass er *term betrachtet, sondern er überlässt diese Analyse 
dem lexikalischen Parser, der sich die jeweils nächsten Character 
ansieht und entscheidet ob und wie die zusammenghören

  while ( nextSymbol( &term, &sym, &value ) ) {

    if( sym == NUMBER )
      push_number( value );

    else if( sym == OPERATOR )
      push_operator( value );  // value ist ein Code für beispielsweise die + Operation
....

Jetzt wird dein ganzer Aufbau schon ein wenig komplexer, weil du nicht 
einfach nur 1-buchstabige Dinge auf deinem Stack verwalten musst, 
sondern weil da jetzt ein buntes Mischmasch aus Zahlen und Operationen 
auf dem Stack verwaltet werden muss.
Dazu brauchst du aber dann auch eine entsprechende Datenstruktur, mit 
der du das kannst. Dein Stack ist dann nicht mehr einfach nur ein Array 
von char. Sondern dein Stack könnte dann zb so aussehen

struct exprStackItem
{
  unsigned char itemType;
  int           itemValue;
};

struct exprStackItem exprStack[50];    // Platz für 50 einträge am Stack
int exprStackPointer;

#define STACK_NUMBER_ITEM         1
#define STACK_OPERATOR_ITEM       2
#define STACK_OPEN_PAREN_ITEM     3

void pushNumber( int value )
{
  exprStack[exprStackPointer].itemType = STACK_NUMBER_ITEM;
  exprStack[exprStackPointer++].itemValue = value;
}

void pushOperator( int operatorCode )
{
  exprStack[exprStackPointer].itemType = STACK_OPERATOR_ITEM;
  exprStack[exprStackPointer++].itemValue = value;
}

void pushOpenParen( void )
{
  exprStack[exprStackPointer].itemType = STACK_OPEN_PAREN_ITEM;
}

....

Aber: dadurch, dass du die Dinge jetzt sauber auf dem Stack liegen hast, 
kannst du zb die angegebenen Ausdrücke auch tatsächlich irgendwann 
ausrechnen. Dein eine Integer-Zahl ist bei dir am Stack jetzt auch 
wirklich eine Integer Zahl und nicht einfach nur einzelne 'Buchstaben'.

[Yalu X. (yalu) (Moderator)]

Hier hat sich außerdem ein Fehler eingeschlichen:

          while (priority(*term) <= priority(top()) && !isEmpty()) {

Du musst die beiden Operanden der &&-Verknüpfung vertauschen, denn du
willst zuerst sicherstellen, dass der Stack mindestens ein Element
enthält, bevor dieses mit top() gelesen wird:

          while (!isEmpty() && priority(*term) <= priority(top())) {

[ldn (Gast)]

Okay, danke schonmal ihr beide.

Ich probiere noch ein bischen herum und wenn sich weitere Fragen auftun 
komme ich hierher zurück.

Ich habe noch was gefunden: 
https://en.wikipedia.org/wiki/Shunting-yard_algorithm
Wäre ja das was ich will

[Karl H. (kbuchegg)]

ldn schrieb:

> Ich habe noch was gefunden:
> https://en.wikipedia.org/wiki/Shunting-yard_algorithm
> Wäre ja das was ich will

Aber auch hier gilt

To convert, the program reads each symbol in order and does something based on that symbol.

'symbol'(!)
nicht Einzelbuchstaben. Egal wie du es drehst und wendest, 
sinnvollerweise kommst du um einen lexikalischen Parser nicht herum. Der 
ist ja nicht weiter schwer zu schreiben. Eine Zahl ist etwas, das mit 
einer Ziffer beginnt und aus weiteren Ziffern besteht, bis zum ersten 
Character der eben keine Ziffer mehr ist (für Integer. Bei Floating 
Point Zahlen wird das dann schon aufwändiger)
In deinem obigen Beispiel nimmst du noch für ')' und '(' ein eigenes 
Symbol, weil die in deinem Stack basiertem Code eine besondere Bedeutung 
haben. Ok, das müsste man nicht unbedingt.

und alles andere ist dann einfach ein Operator-Symbol