Evaluating postfix expression using recursion

Question

I need an algorithm for evaluating postfix expression using recursion. In this postfix expression an operand can be of more than one digit. A space is used to distinguish between two operands. So an expression '45 68 +' is valid.

I thought of evaluating it in reverse direction but I think that should not be correct.

Can someone help me with just the algorithm.

Thanks in advance.

Answer 1

Doesn't strike me as a recursive-friendly problem. But I'm sure it could be done that way.

Two approaches occur to me:

Option #1: Make functional recursion calls and returns match the stack push and pop operations described on the Wiki.

Down side to this approach is that you'll quickly find that the returned data from the function can be fairly complex. It'll probably be an operator. Maybe with an optional operand (IE: number). You'll be returning structures/objects that maybe should have operations (methods) on them.

Option #2: Each recursive call processes the next character of the input stream.

I think this approach would pass in as parameters the stack and maybe an "accumulator" for the current number -- to accumulate digits into a number before pushing it on the stack. There would be one massive tail recursion numeric result returned.

This approach is really just rewriting a loop as recursion.

Either way, figuring it out yourself should be challenging and educational!

Answer 2

Following is a sort of pseudo code which will work for postfix expressions with +/- . I think you can further extend the idea. If you still face difficulty then mail me to 2shanks.p@gmail.com as I am not regular on this site.

void recursivePostfix(char* expr)  
{  
if(!expr)   return;  

bool flag=true;
static double result=0;
double v1=result, v2=0, dec=0;
char oper='0';
int i=0, state=1;

do
{
    if('0' != oper)
    {
        switch(oper)
        {
            case '+': result=v1+v2; break;
            case '-': result=v1-v2; break;
            case '*': result=v1*v2; break;
            case '/': result=v1/v2; break;
        }
        oper = '0';
        v1 = result;
        v2 = 0;
        recursivePostfix(expr+i);
    }

    if(SPACE_CHAR == *(expr+i) && state++)
        continue;

    switch(state)
    {
        case 1:
            v1 = v1*10 + (expr[i]-'0'); break;
        case 2:
            v2 = v2*10 + (expr[i]-'0'); break;
        case 3:
            oper = *(expr+i);
    }  
}while(0 != *(expr+i++));
cout << result;

}