Advertisement
Rakibul_Ahasan

Convert Infix To Prefix Notation

Aug 27th, 2019
179
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.18 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<stdlib.h>      /* for exit() */
  3. #include<ctype.h>     /* for isdigit(char ) */
  4. #include<string.h>
  5.  
  6. #define SIZE 100
  7.  
  8. char stack[SIZE];
  9. int top = -1;
  10.  
  11. void push(char item)
  12. {
  13.     if(top >= SIZE-1)
  14.     {
  15.         printf("\nStack Overflow.");
  16.     }
  17.     else
  18.     {
  19.         top = top+1;
  20.         stack[top] = item;
  21.     }
  22. }
  23.  
  24. char pop()
  25. {
  26.     char item ;
  27.  
  28.     if(top <0)
  29.     {
  30.         printf("stack under flow: invalid infix expression");
  31.         getchar();
  32.         exit(1);
  33.     }
  34.     else
  35.     {
  36.         item = stack[top];
  37.         top = top-1;
  38.         return(item);
  39.     }
  40. }
  41.  
  42. int is_operator(char symbol)
  43. {
  44.     if(symbol == '^' || symbol == '*' || symbol == '/' || symbol == '+' || symbol =='-')
  45.     {
  46.         return 1;
  47.     }
  48.     else
  49.     {
  50.     return 0;
  51.     }
  52. }
  53.  
  54. int precedence(char symbol)
  55. {
  56.     if(symbol == '^')
  57.     {
  58.         return(3);
  59.     }
  60.     else if(symbol == '*' || symbol == '/')
  61.     {
  62.         return(2);
  63.     }
  64.     else if(symbol == '+' || symbol == '-')
  65.     {
  66.         return(1);
  67.     }
  68.     else
  69.     {
  70.         return(0);
  71.     }
  72. }
  73.  
  74. void InfixToPostfix(char infix_exp[], char postfix_exp[])
  75. {
  76.     int i, j;
  77.     char item;
  78.     char x;
  79.  
  80.     push('(');    
  81.     strcat(infix_exp,")");
  82.  
  83.     i=0;
  84.     j=0;
  85.     item=infix_exp[i];
  86.  
  87.     while(item != '\0')
  88.     {
  89.         if(item == '(')
  90.         {
  91.             push(item);
  92.         }
  93.         else if( isdigit(item) || isalpha(item))
  94.         {
  95.             postfix_exp[j] = item;
  96.             j++;
  97.         }
  98.         else if(is_operator(item) == 1)  
  99.         {
  100.             x=pop();
  101.             while(is_operator(x) == 1 && precedence(x)>= precedence(item))
  102.             {
  103.                 postfix_exp[j] = x;  
  104.                 j++;
  105.                 x = pop();      
  106.             }
  107.             push(x);
  108.  
  109.             push(item);                
  110.         }
  111.         else if(item == ')')        
  112.         {
  113.             x = pop();                  
  114.             while(x != '(')    
  115.             {
  116.                 postfix_exp[j] = x;
  117.                 j++;
  118.                 x = pop();
  119.             }
  120.         }
  121.         else
  122.         {
  123.             printf("\nInvalid infix Expression.\n");      
  124.             getchar();
  125.             exit(1);
  126.         }
  127.         i++;
  128.  
  129.         item = infix_exp[i];
  130.     }
  131.     if(top>0)
  132.     {
  133.         printf("\nInvalid infix Expression.\n");    
  134.         getchar();
  135.         exit(1);
  136.     }
  137.     if(top>0)
  138.     {
  139.         printf("\nInvalid infix Expression.\n");  
  140.         getchar();
  141.         exit(1);
  142.     }
  143.     postfix_exp[j] = '\0';
  144. }
  145.  
  146. int main()
  147. {
  148.     char infix[SIZE], postfix[SIZE];
  149.  
  150.    
  151.     gets(infix);
  152.  
  153.     InfixToPostfix(infix,postfix);
  154.     printf("Postfix Expression: ");
  155.     puts(postfix);
  156.  
  157.     return 0;
  158. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement