Postfix vs Prefixo

5

Eu li em alguns lugares que o Postfix é mais fácil de avaliar & mais fácil de converter em código do que prefixo.

Entendo que, se você analisar uma expressão de prefixo da esquerda para a direita, talvez não seja possível avaliar diretamente (pois alguns operandos também podem ser expressões de prefixo); mas se você analisar a expressão de prefixo da direita para a esquerda, ela se tornará tão simples quanto analisar uma expressão de postfix da esquerda para a direita.

Ainda há uma diferença que eu estou sentindo falta?

    
por nikel 11.12.2016 / 02:26
fonte

2 respostas

6

A diferença está nos modelos de execução padrão dos idiomas de prefixo e postfix. Uma linguagem de prefixo como, digamos, um Lisp é tipicamente baseada em uma avaliação baseada em substituição de nó inspirada em cálculo lambda. Então, para avaliar

+ 1 * 3 2

Eu primeiro faria uma árvore

+
1 *
   3 2

Em seguida, substitua as expressões internas para simplificar

+
1 6

7

Para obter este modelo de avaliação, devo analisar em uma árvore. Os idiomas do postfix por contraste tendem a ser baseados em operadores de pilha. Quando eu escrevo

1 3 2 * +

Eu não estou escrevendo 2 operações (mais e tempos), mas 5, porque cada numeral representa "empurre o número correspondente para a pilha". Porque eles serão executados como uma série de operadores em uma pilha que eu possa analisar como uma lista simples de símbolos ao invés de uma árvore, o que é um pouco mais fácil.

Agora é verdade que você poderia impor uma semântica de pilha em uma notação de prefixo e assim tratar o prefixo como "postfix escrito de trás para frente" e vice-versa. ". Portanto, não há diferença essencial em quão difícil é analisar o prefixo e o postfix em si mesmos. Modelos de execução bastante diferentes requerem ASTs diferentes, alguns dos quais são mais difíceis de analisar do que outros, e esses modelos de execução geralmente são escritos em prefixo ou em postfix dependendo.

Em resposta à pergunta

A razão da preferência é que uma AST baseada em árvore com uma semântica substitucional faz incluir variável, função, classe, quaisquer que sejam as declarações muito naturais (o cálculo lambda foi, afinal, o primeiro deles). Considerando que não há nenhuma maneira legal que eu possa ver de colocar essas coisas em uma semântica puramente baseada em pilha (na verdade todas as linguagens postfix que eu conheço terão notação não-postfix e, portanto, uma "árvore com listas planas para ramificações" AST para incluir coisas como declarações de função ou funções anônimas / estruturas de controle).

Você pode ter um idioma postfix sem essas estruturas e ser completo (basta usar o cálculo SKI), mas elas são muito úteis.

    
por 11.12.2016 / 03:20
fonte
0

Você não precisa analisar uma sequência de notação de prefixo da esquerda para a direita para avaliá-la. Você não precisa convertê-lo para uma AST (ou qualquer outra árvore) para avaliação. A avaliação pode ser bastante semelhante à avaliação do RPN, na verdade.

Com o RPN, você segue uma estrutura básica:

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

Com a notação de prefixo, você normalmente usa recursão em vez de uma pilha explícita. O padrão parece algo como:

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

Por exemplo, aqui está um código (de trabalho) para fazer isso em 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 << "> ";
    }
}

Isso é um pouco mais longo / complexo que a maioria dos avaliadores de postfix, mas pelo menos parte da complexidade extra é porque ela faz um pouco mais do que a maioria. Em particular, ele suporta definição de variáveis, atribuição de valores a elas e descarte todos os valores quando estiver pronto (onde a maioria dos avaliadores de postfix eu vi apenas avaliar uma única expressão, então imprima o que estiver no topo da pilha).

    
por 11.12.2016 / 22:53
fonte