Pages

Related Posts with Thumbnails
Infix to Postfix – C Programming And Algorithom >> Codes-N-Tricks
Content feed Comments Feed

Infix to Postfix – C Programming And Algorithom

Posted by Soham Saturday, September 11, 2010

This Proram makes an Infix expression to its Postfix form.

Infix to postfix
  1. #include<stdio.h>
  2. #include<string.h>
  3.  
  4. #define size 10
  5.  
  6. struct stack
  7. {
  8.   char stkel[size];
  9.   int tos;
  10. };
  11.  
  12. struct stack stk;
  13. int ele;
  14. char infix[50],output[50];
  15.  
  16. void push(struct stack *ps,char ele);
  17. char pop(struct stack *ps);
  18. void show_stack(struct stack *ps);
  19. void show_output(char output[]);
  20. int prec(char);
  21.  
  22. int main()
  23. {
  24.     int i=0,j=0,k=0,length;
  25.     char temp;
  26.     struct stack *ps;
  27.     FILE *fp;
  28.  
  29.     fp=fopen("data1.txt","r");
  30.     if(fp==NULL)
  31.     {
  32.         printf("\nError Openning File\n");
  33.         exit(1);
  34.     }
  35.     else
  36.         printf("Data from the file data1.txt has been taken.\n");
  37.  
  38.     ps=&stk;
  39.     ps->tos=-1;
  40.  
  41.     while(!feof(fp))
  42.     {
  43.         ps->tos=-1;j=0;
  44.         fscanf(fp,"%s\n",infix);
  45.         printf("\nThe infix expresson is %s\n",infix);
  46.         length=strlen(infix);
  47.     
  48.         printf("\nInp\t\tPostfx\t\t\tStk\n");
  49.         
  50.         for(i=0;i<length;i++)
  51.         {
  52.                 printf("%c\t\t",infix[i]);//Input string Printed
  53.                                 //Numbers are added to the out put string
  54.                 if(infix[i]!='+' && infix[i]!='-' && infix[i]!='*' && infix[i]!='/' && infix[i]!='^' && infix[i]!='$' && infix[i]!=')' && infix[i]!='(' )
  55.                 {
  56.                     output[j]=infix[i];
  57.                     j++;
  58.                 }
  59.                                 //If an operator or a bracket is encountered
  60.                 else
  61.                 {
  62.                     if(ps->tos==-1) //If there are no elements in the stack,the operator added to stack
  64.                     {
  65.                     push(ps,infix[i]);
  66.                     }
  67.                     else
  68.                     {       //Operators or pushed or poped based on the precedence
  69.                         if(infix[i]!=')' && infix[i]!='(')
  70.                         {
  71.                             if(prec(infix[i]) <= prec(ps->stkel[(ps->tos)]))
  72.                             {
  73.                             temp=pop(ps);
  74.                             output[j]=temp;
  75.                             j++;
  76.                             push(ps,infix[i]);
  77.                             }
  78.                             else
  79.                             {
  80.                               push(ps,infix[i]);
  81.                             }
  82.                         }
  83.                         else    //if bracket occurs
  84.                         {
  85.                             if(infix[i]=='(')
  86.                             {
  87.                               push(ps,infix[i]);
  88.                             }
  89.                             if(infix[i]==')')
  90.                             {
  91.                               temp=pop(ps);
  92.                               while(temp!='(')
  93.                               {
  94.                                 output[j]=temp;
  95.                                 j++;
  96.                                 temp=pop(ps);
  97.                               }
  98.                             }
  99.                         }
  100.                     }
  101.                 }
  102.                 output[j]='\0';
  103.                 show_output(output);
  104.                 printf("\t\t\t");
  105.                 show_stack(ps);
  106.    
  107.  
  108.         }
  109.  
  110.         //rest of the elemets of stack added to postfix string
  111.         while(ps->tos!=-1)
  112.         {
  113.             output[j++]=pop(ps);
  114.             output[j]='\0';
  115.             printf("\t\t");
  116.             show_output(output);
  117.             printf("\t\t\t");
  118.             show_stack(ps);
  119.         }
  120.  
  121.         printf("\nThe postfix expression is\t");
  122.          for(i=0;i<length;i++)
  123.             printf("%c",output[i]);
  124.         printf("\n");
  125.     }
  126.     return 0;
  127.  
  128. }
  129. //Functions for operations on stack
  130.  
  131. void push(struct stack *ps,char ele)
  132. {
  133.     ps->tos++;
  134.     ps->stkel[ps->tos]=ele;
  135. }
  136.  
  137. char pop(struct stack *ps)
  138. {
  139.     char var;
  140.     var=ps->stkel[ps->tos];
  141.     ps->tos--;
  142.     return var;
  143. }
  144.  
  145. //showing postfix string
  146. void show_output(char output[])
  147. {
  148.     int i;
  149.     for(i=0;output[i]!='\0';i++)
  150.         printf("%c",output[i]);
  151. }
  152.  
  153. //showing the elements of stack
  154. void show_stack(struct stack *ps)
  155. {
  156.     int x=0;   
  157.     if(ps->tos>-1)
  158.         while(x<=ps->tos)
  159.         {
  160.             printf("%c",ps->stkel[x]);
  161.             x++;
  162.         }
  163.     printf("\n");
  164. }
  165.  
  166. //Function to get the precedence of an operator
  167.  
  168. int prec(char symbol)
  169. {
  170.  
  171. if(symbol== '(')
  172. return 0;
  173. if(symbol== ')')
  174. return 0;
  175. if(symbol=='+' || symbol=='-')
  176. return 1;
  177. if(symbol=='*' || symbol=='/')
  178. return 2;
  179. if(symbol=='^')
  180. return 3;
  181. //return 0;
  182. }
Further discussion will be carried out later.  Any Suggestion is solicited.

, , | edit post

0 Responses to Infix to Postfix – C Programming And Algorithom

Post a Comment

SyntaxHighlighter

E-Mail Subscription

Enter your email address:

Subscribe & get Regular E-Mail Updates From Codes-N-Tricks.
Delivered by FeedBurner

Share with Orkut

Loading

Recent Posts

About Us

Soham
View my complete profile