# 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?

• One thing you might be missing is that it is really difficult to read a file from right (end) to left (beginning). Dec 11, 2016 at 7:21
• @BartvanIngenSchenau Why should the be "really difficult". You mean like subtraction is more difficult than addition?
– user188153
Dec 11, 2016 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? Dec 11, 2016 at 12:52
• 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. Dec 11, 2016 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. Dec 12, 2016 at 7:55

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? Dec 11, 2016 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 :) Dec 17, 2016 at 10:49

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. Dec 17, 2016 at 10:51