CODEWITHSUNDEEP
javarecursionpostfix-notation
Keen Sage
Keen Sage

Reputation: 1949

Evaluating postfix expression using recursion

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.

Upvotes: 2

Views: 5934

Answers (3)

juanifioren
juanifioren

Reputation: 683

I just code this for an interview, so here is my solution using Python:

def recursive_postfix(s):
    s = s.split(' ')
    if len(s) == 1:
        return s[0]
    res = None
    for i in range(len(s)):
        if s[i] in ['+', '-', '*', '/']:
            res = eval(f'{s[i-2]}{s[i]}{s[i-1]}')
            break
    s = s[0:i-2] + [str(res)] + s[i+1:]
    return recursive_postfix(' '.join(s))

assert recursive_postfix('2 2 + 1 *') == '4' # (2 + 2) * 1
assert recursive_postfix('3 4 2 + * 5 *') == '90' # 3 * (4 + 2) * 5
assert recursive_postfix('7 2 2 * -') == '3' # 7 - (2 * 2)

Upvotes: 0

paper.plane
paper.plane

Reputation: 1197

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 [email protected] 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;

}

Upvotes: 1

Jeff Grigg
Jeff Grigg

Reputation: 1014

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!

Upvotes: 2

Related Questions