Postfix vs Prefisso

La differenza è nei modelli di esecuzione predefiniti dei linguaggi prefisso e postfix. Un linguaggio prefissato come dire che un Lisp è tipicamente basato su una valutazione basata sulla sostituzione del nodo ispirata al calcolo lambda. Quindi per valutare

+ 1 * 3 2

Vorrei prima creare un albero

+
1 *
   3 2

Quindi sostituisci le espressioni interne per semplificare

+
1 6

7

Per ottenere questo modello di valutazione devo analizzare un albero. Le lingue Postfix al contrario tendono ad essere basate su operatori di stack. Quando scrivo

1 3 2 * +

Non sto scrivendo 2 operazioni (più e volte) ma 5, perché ogni numero rappresenta "spinge il numero corrispondente nello stack". Poiché saranno eseguiti come una serie di operatori in una pila, posso analizzare come una semplice lista di simboli piuttosto che un albero, che è un po 'più semplice.

Ora è sicuramente vero che si potrebbe imporre una semantica dello stack su una notazione prefissata e trattare quindi il prefisso come "postfix scritto all'indietro" e viceversa si potrebbe imporre una semantica di sostituzione su una notazione postfix e quindi trattare postfix come "prefisso scritto all'indietro" ". Quindi non c'è alcuna differenza essenziale in quanto è difficile analizzare prefissi e suffissi in se stessi. Piuttosto diversi modelli di esecuzione richiedono AST diversi, alcuni dei quali sono più difficili da analizzare rispetto ad altri, e questi modelli di esecuzione di solito sono scritti in prefissi o suffissi a seconda.

In risposta alla domanda

La ragione di preferenza è che un AST basato su alberi con una semantica sostitutiva rende molto variabile la variabile, la funzione, la classe, qualsiasi dichiarazione (il calcolo lambda era dopo tutto il primo di questi). Considerando che non c'è un modo carino per vedere di mettere queste cose in una semantica puramente stack (in effetti tutte le lingue postfix di cui sono a conoscenza avranno notazione non postfix e quindi un "albero con liste piatte per rami" AST per includere cose come dichiarazioni di funzioni o funzioni anonime / strutture di controllo).

Potresti avere un linguaggio postfisso senza tali strutture ed essere completo (usa solo il calcolo degli SKI) ma sono molto utili.

Non è necessario analizzare una stringa di notazione prefisso da sinistra a destra per valutarla. Non è necessario convertirlo in un AST (o qualsiasi altro albero) per la valutazione. Valutarlo in realtà può essere abbastanza simile alla valutazione dell'RPN, in effetti.

Con RPN, segui una struttura abbastanza semplice di:

while there's more input
    if the next input is an operand, push it on the stack
    else (it should be an operator) evaluate it, using operands on the stack

Con la notazione del prefisso, in genere si utilizza la ricorsione anziché uno stack esplicito. Il modello assomiglia a:

while there's more input
    get an input (should be an operator)
    make N recursive calls to get the operands for that operator
    apply operator to operands to get result

Ad esempio, ecco un codice (funzionante) per farlo in C ++:

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <map>
#include <iterator>

using namespace std; // really would *not* normally do this, but...

void define_var(map<string, int> &v, istringstream& iss) {
    std::string name;
    int value;
    iss >> name >> value;
    v[name] = value;
}                       

int do_op(char op, int val1, int val2) { 
    switch (op) { 
        case '+': return val1 + val2;
        case '-': return val1 - val2;
        case '*': return val1 * val2;
        case '/': return val1 / val2;
        default: 
            string error("Unknown operator: ");
            error += op;
            throw runtime_error(error);
    }
}

bool isoperator(char ch) { 
    return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}

char getop(istream &is) {
    char ch;
    while (isspace(ch = is.peek()))
        is.get(ch);
    ch = is.peek();
    return ch;
}

int eval(istream &is, map<string, int> const &v) { 
    // evaluate an expression. It consists of:
    // an operator followed by operands, or
    // a number, or
    // a variable.
    // 

    char ch = getop(is);

    if (isoperator(ch)) {
        is.get(ch);
        int val1 = eval(is, v);
        int val2 = eval(is, v);
        return do_op(ch, val1, val2);
    }
    if (isdigit(ch)) {
        int val;
        is >> val;
        return val;
    }

    string var_name;
    is >> var_name;
    map<string, int>::const_iterator p = v.find(var_name);
    if (p==v.end()) {
        string problem("Unknown variable: ");
        problem +=var_name;
        throw runtime_error(problem.c_str());
    }
    return p->second;
}

// used only for dumping out the variables.
namespace std { 
    ostream &operator<<(ostream &os, pair<string, int> const &v) {
        return os << v.first << ": " << v.second;
    }
}

int main() {  
    map<string, int> v;

    string temp;
    cout << endl << "> ";
    while (getline(cin, temp)) {
        istringstream iss(temp);

        string op;
        iss >> op;

        if (op == "quit")
            break;
        else if (op == "def") 
            define_var(v, iss);
        else if (op == "show_vars")
            std::copy(v.begin(), v.end(), ostream_iterator<pair<string, int> >(cout, "\n"));
        else {
            // Technically, this isn't right -- it only ungets one 
            // character, not the whole string.
            // For example, this would interpret "this+ 2 3" as "+ 2 3"
            // and give 5 instead of an error message. Shouldn't affect 
            // correct input though.
            // 
            iss.unget();
            cout << endl << eval(iss, v) << endl;
        }
        cout << endl << "> ";
    }
}

Questo è un po 'più lungo / più complesso della maggior parte dei valutatori postfix, ma almeno una parte della complessità extra è perché fa un po' più della maggior parte. In particolare, supporta la definizione di variabili, l'assegnazione di valori e il dumping di tutti i valori quando hai finito (dove la maggior parte dei valutatori postfix ho visto solo valutare una singola espressione, quindi stampare ciò che è in cima alla pila).