4

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?

  • 1
    One thing you might be missing is that it is really difficult to read a file from right (end) to left (beginning). – Bart van Ingen Schenau Dec 11 '16 at 7:21
  • @BartvanIngenSchenau Why should the be "really difficult". You mean like subtraction is more difficult than addition? – qwerty_so Dec 11 '16 at 10:06
  • Should not be difficult for machines i think. If you have the complete expression, go to the last position, start reading backwards? – nikel Dec 11 '16 at 12:52
  • 1
    Ok, it we are speaking of difficulty for the machines, all of these, including infix with parenthesis and function calls, are relatively trivial. If you were implementing in hardware from scratch without a software programming layer, then the relative difficulty might be relevant. – Erik Eidt Dec 11 '16 at 15:50
  • @ThomasKilian: I mean that reading backwards from an initially unknown position is much harder than reading forwards from a known position, especially if all file abstractions are based on reading forwards. – Bart van Ingen Schenau Dec 12 '16 at 7:55
6

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.

  • So, you say that its just because the default execution model for prefix is tree based rather than being stack based? Also what are the reasons to go for a tree based model? – nikel Dec 11 '16 at 12:55
  • I don't have a lot of experience with lambda expressions, so did not get the last paragraph very well. If you could add a few examples that make it simple to understand, that would be great & i will of course accept the answer :) – nikel Dec 17 '16 at 10:49
0

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).

  • It can become even easier if we parse the prefix expression from right to left and evaluate it like a stack. My Question was that since this is as easy as parsing postfix from left to right , why do people say that postfix evaluation is easier. – nikel Dec 17 '16 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.