program to evaluate prefix expression using stack | Using C language | Data Structure |

👨‍💻Write a program to evaluate prefix expression using stack.

Click here >>  evaluate postfix expression using stack

⇨ Steps for Evaluation of Prefix Expression Using Stack:

1. Create a stack to store operands (or values). 
2. Check(scan) the given expression from right to left and do the following for every checked character (or element).
3. If the character (or element) is a number, push it into the stack 
4. If the character (or element) is an operator, pop two operands one by one but change the order of pop them for the operator from the stack to perform an operation and push the result back to the stack.[for better understanding see the code]
5. When the expression is ended (means the upcoming character is NULL), the number in the stack is the final answer.

For Example:

CODE for evaluating Prefix expressions :

    //program to evaluate prefix expression using stack.

    #include <stdio.h>

    #include <stdlib.h>

    #include <ctype.h>

    #include <math.h>

    #include <string.h>

    int stack[20];

    int top = -1; /* Declaring global variable 'top' */

    void push(int x)

    {

       

        stack[++top] = x; /* Here,  ( ++ top ) means that it first Increamet top by 1, then use incremented value of top. */

    }

    int pop()

    {

       

        return stack[top--]; /* Here,  ( top - - ) means that it first use value of top, then top decrement by 1. */

    }

    int main()

    {

       

        char exp[20];

        int i = 0;

        int n1, n2, n3, num;

        printf("Enter the expression :: ");

        gets(exp);

        strrev(exp); /* use strrev() function to reverse string for evaluating Prefix  expressions. [From  string.h  header file]  */

        while (exp[i] != '\0')

        {

       

            if (isdigit(exp[i])) /* isdigit() function checks that entered character is Digit or not. [From  ctyp.h  header file]  */

            {

       

                num = exp[i] - 48;

                push(num);

            }

            else

            {

       

                n2 = pop(); /* NOTE: In prefix evaluation, first n2 then n1 popped */

                n1 = pop();

                switch (exp[i])

                {

       

                case '+':

                {

       

                    n3 = n2 + n1;

                    break;

                }

                case '-':

                {

       

                    n3 = n2 - n1;

                    break;

                }

                case '*':

                {

       

                    n3 = n2 * n1;

                    break;

                }

                case '/':

                {

       

                    n3 = n2 / n1;

                    break;

                }

                case '^':

                {

       

                    n3 = pow(n2, n1); /* pow(x,y) function [From  math.h  header file]  */

                    break;

                }

                case '$':

                {

       

                    n3 = pow(n2, n1);

                    break;

                }

                }

                push(n3);

            }

            i++;

        }

        printf("\nThe result of expression %s  =  %d\n\n", strrev(exp), pop());

        return 0;

    }

OUTPUT: