Postfix vs Prefix

I have read at a few places, that Postfix is easier to evaluate & easier to convert to Code than Prefix.

I understand that if you parse a prefix expression from left to right, you might not be able to evaluate directly(as some operands might be prefix expressions as well); but if you parse the prefix expression from Right to left , it becomes as simple as parsing a postfix expression from left to right.

Is there still a difference that i am missing?

5

The difference is in the default execution models of prefix and postfix languages. A prefix language like say a Lisp is typically based on an lambda calculus inspired node-substitution based evaluation. So in order to evaluate

+ 1 * 3 2

I would first make a tree

+
1 *
   3 2

And then substitute inner expressions to simplify

+
1 6

7

In order to get this evaluation model I must parse into a tree. Postfix languages by contrast tend to be based on stack operators. When I write

1 3 2 * +

I am not writing 2 operations (plus and times) but 5, because each numeral represents “push the corresponding number onto the stack”. Because they will be executed as a series of operators on a stack I can parse then as just a flat list of symbols rather than a tree, which is a bit easier.

Now it is definitely true that you could impose a stack semantics on a prefix notation and so treat prefix as “postfix written backwards” and conversely you could impose a substitution semantics on a postfix notation and so treat postfix as “prefix written backwards”. So there is no essential difference in how difficult it is to parse prefix and postfix in themselves. Rather different execution models require different ASTs, some of which are harder to parse for than others, and these execution models are usually written in either prefix or postfix depending.

In response to question

The reason for preference is that a tree based AST with a substitutional semantics makes including variable, function, class, whatever declarations very natural (the lambda calculus was after all the first of these). Whereas there’s no nice way I can see of putting these things in a purely stack based semantics (indeed all postfix languages I am aware of will have non-postfix notation and thus a “tree with flat lists for branches” AST in order to include things like function declarations or anonymous functions/control structures).

You could have a postfix language without such structures and be complete (just use SKI calculus) but they’re mighty handy.

2

You don’t have to parse a prefix notation string from left to right to evaluate it. You don’t have to convert it to an AST (or any other tree) for evaluation either. Evaluating it can actually be quite similar to evaluating RPN, as a matter of fact.

With RPN, you follow a fairly basic structure of:

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

With prefix notation, you typically use recursion instead of an explicit stack. The pattern looks something like:

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

For example, here’s some (working) code to do that 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 << "> ";
    }
}

This is a little longer/more complex than most postfix evaluators, but at least some of the extra complexity is because it does a bit more than most. In particular, it supports defining variables, assigning values to them, and dumping out all the values when you’re done (where most postfix evaluators I’ve seen just evaluate a single expression, then print out whatever’s on top of the stack).

1

Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa Dịch vụ tổ chức sự kiện 5 sao Thông tin về chúng tôi Dịch vụ sinh nhật bé trai Dịch vụ sinh nhật bé gái Sự kiện trọn gói Các tiết mục giải trí Dịch vụ bổ trợ Tiệc cưới sang trọng Dịch vụ khai trương Tư vấn tổ chức sự kiện Hình ảnh sự kiện Cập nhật tin tức Liên hệ ngay Thuê chú hề chuyên nghiệp Tiệc tất niên cho công ty Trang trí tiệc cuối năm Tiệc tất niên độc đáo Sinh nhật bé Hải Đăng Sinh nhật đáng yêu bé Khánh Vân Sinh nhật sang trọng Bích Ngân Tiệc sinh nhật bé Thanh Trang Dịch vụ ông già Noel Xiếc thú vui nhộn Biểu diễn xiếc quay đĩa Dịch vụ tổ chức tiệc uy tín Khám phá dịch vụ của chúng tôi Tiệc sinh nhật cho bé trai Trang trí tiệc cho bé gái Gói sự kiện chuyên nghiệp Chương trình giải trí hấp dẫn Dịch vụ hỗ trợ sự kiện Trang trí tiệc cưới đẹp Khởi đầu thành công với khai trương Chuyên gia tư vấn sự kiện Xem ảnh các sự kiện đẹp Tin mới về sự kiện Kết nối với đội ngũ chuyên gia Chú hề vui nhộn cho tiệc sinh nhật Ý tưởng tiệc cuối năm Tất niên độc đáo Trang trí tiệc hiện đại Tổ chức sinh nhật cho Hải Đăng Sinh nhật độc quyền Khánh Vân Phong cách tiệc Bích Ngân Trang trí tiệc bé Thanh Trang Thuê dịch vụ ông già Noel chuyên nghiệp Xem xiếc khỉ đặc sắc Xiếc quay đĩa thú vị
Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa
Thiết kế website Thiết kế website Thiết kế website Cách kháng tài khoản quảng cáo Mua bán Fanpage Facebook Dịch vụ SEO Tổ chức sinh nhật