Evaluate Prefix Expression C Program

By | October 26, 2016

Learn How To Evaluate Prefix Expression using Stack in C Programming Language. The Prefix notation is also known as Polish Notation. Before you proceed further with this code, you must know the complete operations of stack data structure.

Prefix To Infix Conversion Example

Prefix Expression: +22

Evaluation: 4

C Program To Evaluate Prefix Expression using Stack Data Structure

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define LIMIT 500

typedef struct prefix_expression
{
      int top;
      int stack[LIMIT];
}stack_structure;

void initialize(stack_structure *temp)
{
      temp->top = -1;
}

void push(stack_structure *temp, int num)
{
      if(temp->top == LIMIT)
      {
            printf("\nStack Overflow\n");
            exit(-1);
      }
      else
      {
            temp->top++;
            temp->stack[temp->top]=num;
      }
}

int pop(stack_structure *temp)
{
      int num;
      if(temp->top < 0)
      {
            printf("\nStack Underflow\n");
            exit(-1);
      }
      num = temp->stack[temp->top];
      temp->top--;
      return num;
}

int top(stack_structure *temp)
{
      return temp->stack[0];
}

void evaluate_prefix(stack_structure *temp, char operator, int x, int y)
{
      int result;
      switch(operator)
      {
            case '-': result = x - y;
                      break;
            case '*': result = x * y;
                      break;
            case '%': result = x % y;
                      break;
            case '/': result = x / y;
                      break;
            case '+': result = x + y;
                      break;
            case '$': result = pow(x, y);
                      break;
      }
      push(temp, result);
}

int find_operator(char ch)
{
      switch(ch)
      {
            case '%': return 20;
            case '/': return 20; 
            case '*': return 20;
            case '-': return 20;
            case '$': return 20;
            case '+': return 20;
            default : return 10;
      }
}

int main()
{
      int x, y, element, length, count;
      char * expression;
      stack_structure expression_stack;
      initialize(&expression_stack);
      printf("\nEnter Prefix Expression:\t");
      scanf("%s", expression);
      length = strlen(expression);
      for(count = length - 1; count >= 0; count--)
      {
            if(expression[count] == '\0' || expression[count] == ' ')
            {
                  continue;
            }
            switch(find_operator(expression[count]))
            {
                  case 20 : x = pop(&expression_stack);
                            y = pop(&expression_stack);
                            evaluate_prefix(&expression_stack, expression[count], x, y);
                            break;
                  case 10 : element = expression[count] - '0';
                            push(&expression_stack, element);
                            break;
            }
      }
      if(expression_stack.top != 0)
      {
            printf("\nInvalid Expression!\n");
            return -1;
      }
      printf("\nEvaluation of Prefix Expression:\t %d\n", top(&expression_stack));
      return 0 ;
}

Output

C Program To Evaluate Prefix Expression using Stack, Structure and Queues

In case you get any compilation errors or any doubts in this C Program For Prefix Expression Evaluation, let us know about it in the Comment Section below.

Recommended Programs
C Program For Quick Sort Algorithm
C Program For Infix To Postfix Conversion
C Program For 8 Queens Algorithm Problem
C Program For Prefix To Infix Conversion
C Program For Postfix To Prefix Conversion
C Program To Evaluate Postfix String using Stack
C Program For Infix To Prefix Conversion
C Program For Postfix To Infix Conversion
C Program For Union and Intersection of Two Sets
C Program To Implement Queue using Linked List

Let's Discuss