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