Prefix Evaluation

                      PREFIX EVALUATION

View/Download

ALGORITHM

1. Scan the Prefix expression right to left.

1.push all operands into stack until an operator is encountered.

2.  when an operator op is encountered.

2.1 pop the last two operands say Y and X off the stack and apply the operation Y op X- order of operands is important

2.2 push the result of the operation back on the stack to be used as an operand later.

2.  When end of expression is reached one operand remains on the stack - it is the final result. Pop the value from stack.

PROGRAM

#include

#include

#include

#include

int arr[100];

int top=-1;

void push(int c)

{

     top++;

     arr[top]=c;

}

int pop()

{

        int c;

        c=arr[top];

        top--;

        return c;

    

}

int main()

{

    char prefix[100];

    int i=0;

    int op1,op2,res,val;

    printf("Enter the prefix expression:");

    scanf("%s",prefix);

    for(i=strlen(prefix)-1;i>=0;i--)

     {

         switch(prefix[i])

          {

                  case'+':op1=pop();

                          op2=pop();

                          res=op1+op2;

                          push(res);

                          break;

                  case'-':op1=pop();

                          op2=pop();

                          res=op1-op2;

                          push(res);

                          break;

                  case'*':op1=pop();

                          op2=pop();

                          res=op1*op2;

                          push(res);

                          break;                      

                  case'/':op1=pop();

                          op2=pop();

                          res=op1/op2;

                          push(res);

                          break;                                              

                 default:printf("Enter the value of %c:",prefix[i]);

                         scanf("%d",&val);

                         push(val);

                         break;

             }

      }

    

printf(" The Given prefix expression is: %s\n",prefix);

printf("Result after evaluation is :%d",arr[top]);

getch();

}                      

         

                              

                                                       

View/Download