# Algorithm for recursive evaluation of postfix expressions

I'm reading Sedgewick's book on algorithms in C and I'm looking for an algorithm to evaluate postfix expressions (addition and multiplication only) without using a stack. I tried to implement one but I always get nowhere.

I have a simple C implementation for prefix evaluation

``````int eval()
{
int x = 0;

while (a[i] == ' ')
i++;
if (a[i] == '+')
{
i++;
return eval() + eval();
}
if (a[i] == '*')
{
i++;
return eval() * eval();
}
while ( (a[i] >= '0') && (a[i] <= '9'))
x = 10*x + (a[i++]-'0');
return x;
}
``````

and I was wondering if it's possible to do something as elegant as this but for postfix evaluation.

• Any reason why you don't want to use a stack for postfix? Part of the reason for postfix is the efficient use of a stack. – user40980 Dec 3 '13 at 17:33
• This is how the exercise is being formulated. I guess I can use the stack as long as I write a recursive function. It's a chapter about recursion and I think the author intends for the reader to get familiarized with recursion. – caisah Dec 3 '13 at 20:30
• Have you tried asking your instructor then? They've got a better idea of the answer they are trying to extract from the exercise than we do. One of the 'problems' with asking about homework on P.SE is that we tend to be a bit more 'pragmatic' in our solutions much of the time. You want elegance? Use a stack. Reinvesting the wheel and doing things the hard way is often antithetical to the mindset of the non-academic programmer. – user40980 Dec 3 '13 at 20:34
• I don't have an instructor I'm learning by myself and this is why I asked here. Anyway I realized this kind of coding is not meant for production, it has academic purpose only. Anyways, I was curious if some more experience programmer could show me a different approach before squeezing my brains out. – caisah Dec 3 '13 at 20:44

I wouldn't exactly call using a global variable as a string index counter 'elegant', but in a nutshell: No, you can't, because you have no idea how to combine the various numbers you find until you get to the operators. Until you do, you have to store them somewhere - and to get the right result, whatever your storage strategy is will ultimately boil down to stack semantics.

• I disagree. It is possible, however it would require that the returning recursive method both returns the calculated value as well as the index to read the next term. – Neil Dec 3 '13 at 15:31
• It's possible to do without using a user-defined stack data structure, but you're still storing the operands on the run-time stack of your programming environment. Obviously, this is usually better than hacking together your own stack structure, but to me, that's still "using a stack". – Kilian Foth Dec 3 '13 at 15:34
• I would contend that for evaluating a postfix expression, using recursion vs using a stack (either user defined or existing library) - the recursion would be less elegant - it boils down to if you are storing numbers on the stack or operands in recursion. I would advocate that the simplicity and of the number stack would be easier to comprehend and more elegant than recursion. Though, thats certainly opinion. – user40980 Dec 3 '13 at 16:33
• Certainly using recursion to do this sort of defeats the purpose of using post-fix in the first place since it is meant to be easily handled with a simple stack, however recursion itself has a call stack with local variables which can have the same effect. It would simply be far less efficient. – Neil Dec 3 '13 at 16:35
• @MichaelT Thanks for the comment. This is exactly what I was referring to, when I used the word elegant in the question. @ Neil You are suggesting some kind of tail recursion, right? – caisah Dec 3 '13 at 16:50

you pass the top 2 in the stack as parameter at each point, this way when you get to an operator you go up the stack when you see a value you go down the stack and when you get back you try again:

here is the magic:

``````eval(int x1, int x2)
{
do{
int x = 0;
while (a[i] == ' ')
i++;
if (a[i] == '+')
{
i++;
return x2+x1;// go up the stack with the resulting value
}
if (a[i] == '*')
{
i++;
return x1*x2;
}
while ( (a[i] >= '0') && (a[i] <= '9'))
x = 10*x + (a[i++]-'0');
x2 = eval(x2, xt); // replace the old top with the result and try again
}while(true);
}
``````

you just need to add 2 functions to handle the errors when operators appear as the first 2 terms:

``````eval()
{
int x = 0;
while (a[i] == ' ')
i++;
if (a[i] == '+')
{
i++;
return ERROR;
}
if (a[i] == '*')
{
i++;
return ERROR;
}
while ( (a[i] >= '0') && (a[i] <= '9'))
x = 10*x + (a[i++]-'0');
return eval(x);
}

eval(int x1)
{
int x = 0;
while (a[i] == ' ')
i++;
if (a[i] == '+')
{
i++;
return ERROR;
}
if (a[i] == '*')
{
i++;
return ERROR;
}
while ( (a[i] >= '0') && (a[i] <= '9'))
x = 10*x + (a[i++]-'0');
return eval(x1, x);
}
``````

and I was wondering if it's possible to do something as elegant as this but for postfix evaluation.

Postfix notation isn't meant to be processed with a call stack or recursion or really anything of that nature. Its designed for nice, tight implementations that just have a simple loop and a stack next to it. These fall into the realm of stack machines and are often found in embedded systems because of their simplicity. You find things like forth, postscript and the jvm as very successful stack machines (see Wikipedia - Category stack based virtual machines) along with venerable HP rpn calculator.

The elegance of postfix can be seen in the simple loop:

``````while not end of file
if var is not operand
push var
else if var is '+'
pop into v1
pop into v2
push v1 + v2
else if var is '*'
pop into v1
pop info v2
push v1 * v2
``````

And thus you go through and implement all the operands and you're done. `dc` has 27 operands (things like print (pop and print) `P`, print (just print) `p`, print the stack `f`, clear the stack `c`, etc...). You can read them at dc.1 man page. I will admit there are some more elegant structures for implementing the operands rather than a huge if else if cascade depending on the language... but you get the idea.

The elegance of the system is its simplicity. You don't have to worry about stack frames, calling conventions, and the like when implementing it. You've got a stack and a variable or two.

I would consider the problem as:

• a parsing problem. read some good compiler text book like the Dragon book. So parse your expression into some Abstract Syntax Tree sitting in the virtual address space of your process.

• then, evaluate that AST (in some environment).

The above approach fits for any expression-like language (not only postfix, but also prefix, or infix, etc...).

Alternatively, a postfix expression can be considered as some bytecode for a stack automaton (or pushdown automaton) based interpreter.

Definition: postfix = identifier | <postfix> <postfix> <operator>

To evaluate a postfix expression, we scan it from the last character to the first one in the expression, then perform the operation indicated by the last character on the two operands on the left, evaluated recursively.

``````char *a;
int i = strlen(a)-1;
int eval()
{
int x = 0;
int factor = 1;
while (a[i] == ' ') i--;
if (a[i] == '+')
{ i--;  return eval() + eval(); }
if (a[i] == '*')
{ i--; return eval() * eval(); }
while ('0' <= a[i] && a[i] <= '9')
{ x = x + (a[i--] - '0') * factor;  factor *= 10; }
return x;
}
``````