Algoritmo per la valutazione ricorsiva delle espressioni postfisse

Non chiamerei esattamente una variabile globale come un contatore di indici stringa "elegante", ma in poche parole: No, non puoi, perché non hai idea di come combinare i vari numeri che trovi finché non ottieni agli operatori. Fino a quando non lo fai, devi memorizzarli da qualche parte - e ottenere il risultato giusto, qualunque sia la tua strategia di storage finirà per impilare la semantica.

passi i primi 2 nella pila come parametro in ogni punto, in questo modo quando arrivi a un operatore salirai nello stack quando vedi un valore che vai giù nello stack e quando torni provi di nuovo:

ecco la magia:

eval(int x1, int x2)
{
 do{
   int x = 0;
   while (a[i] == ' ')
     i++;
   if (a[i] == '+')
    {
      i++;
      return x2+x1;// go up the stack with the resulting value
    }
   if (a[i] == '*')
    {
      i++;
      return x1*x2;
    }
   while ( (a[i] >= '0') && (a[i] <= '9'))
      x = 10*x + (a[i++]-'0');
   x2 = eval(x2, xt); // replace the old top with the result and try again
 }while(true);
}

Hai solo bisogno di aggiungere 2 funzioni per gestire gli errori quando gli operatori appaiono come i primi 2 termini:

eval()
{
 int x = 0;
  while (a[i] == ' ')
    i++;
 if (a[i] == '+')
    {
      i++;
      return ERROR;
    }
  if (a[i] == '*')
    {
      i++;
      return ERROR;
    }
  while ( (a[i] >= '0') && (a[i] <= '9'))
    x = 10*x + (a[i++]-'0');
  return eval(x);
}

eval(int x1)
{
 int x = 0;
  while (a[i] == ' ')
    i++;
 if (a[i] == '+')
    {
      i++;
      return ERROR;
    }
  if (a[i] == '*')
    {
      i++;
      return ERROR;
    }
  while ( (a[i] >= '0') && (a[i] <= '9'))
    x = 10*x + (a[i++]-'0');
  return eval(x1, x);
}

and I was wondering if it's possible to do something as elegant as this but for postfix evaluation.

La notazione Postfix non è pensata per essere elaborata con uno stack di chiamate o ricorsione o in realtà qualcosa di quella natura. È progettato per implementazioni semplici e strette con un semplice loop e uno stack accanto. Questi rientrano nel regno delle macchine stack e spesso si trovano nei sistemi embedded a causa della loro semplicità. Trovi cose come avanti, postscript e jvm come macchine stack di grande successo (vedi Wikipedia - Macchine virtuali basate su stack di categorie ) insieme al venerabile HP calcolatrice rpn .

L'eleganza di postfix può essere vista nel ciclo semplice:

while not end of file
    read into var
    if var is not operand
        push var
    else if var is '+'
        pop into v1
        pop into v2
        push v1 + v2
    else if var is '*'
        pop into v1
        pop info v2
        push v1 * v2

E così si passa e si implementano tutti gli operandi e il gioco è fatto. dc ha 27 operandi (cose come print (pop e print) P , print (just print) p , stampa lo stack f , cancella lo stack c , ecc ...). Puoi leggerli alla pagina man dc.1 . Devo ammettere che ci sono alcune strutture più eleganti per implementare gli operandi piuttosto che un enorme se non altro se la cascata dipende dalla lingua ... ma l'idea è stata trovata.

L'eleganza del sistema è la sua semplicità. Non devi preoccuparti di impilare cornici, chiamare convenzioni e simili quando lo implementa. Hai uno stack e una variabile o due.

Considererei il problema come:

• un problema analizzando . leggi alcuni buoni libri di testo come il libro dei draghi . Analizza quindi la tua espressione in un Abstract Syntax Tree seduto nello spazio degli indirizzi virtuali del tuo processo.

• quindi, valuta AST (in qualche ambiente).

L'approccio sopra si adatta a qualsiasi linguaggio di espressione (non solo postfix, ma anche prefisso, o infisso, ecc ...).

In alternativa, un'espressione postfissa può essere considerata come un bytecode per un automa di stack (o automa pushdown ) interprete basato.

Definizione: postfix = identificatore | < suffisso > < suffisso > < operatore >

Per valutare un'espressione postfissa, scansioniamo dall'ultimo carattere al primo nell'espressione, quindi eseguiamo l'operazione indicata dall'ultimo carattere sui due operandi a sinistra, valutato in modo ricorsivo.

char *a;
int i = strlen(a)-1;
int eval()
{
  int x = 0;
  int factor = 1;
  while (a[i] == ' ') i--;
  if (a[i] == '+')
  { i--;  return eval() + eval(); }
  if (a[i] == '*')
  { i--; return eval() * eval(); }
  while ('0' <= a[i] && a[i] <= '9')
  { x = x + (a[i--] - '0') * factor;  factor *= 10; }
  return x;
}