Promi_38

Infix to postfix conversion(without linked list)

Nov 21st, 2020 (edited)
45
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.82 KB | None | 0 0
  1. //Infix to postfix conversion
  2. // space in infix expression won't be acceptable
  3.  
  4. #include<stdio.h>
  5. #include<stdlib.h>
  6. #include<string.h>
  7.  
  8. #define n 1000000
  9. char a[n];
  10. int size = -1;
  11.  
  12. void push(char x)
  13. {
  14.     if(size == n-1) printf("Full\n");
  15.     else
  16.     {
  17.         size++;
  18.         a[size] = x;
  19.     }
  20. }
  21.  
  22. char pop()
  23. {
  24.     char x = -1;
  25.     if(size == -1) printf("Empty\n");
  26.     else
  27.     {
  28.         x = a[size];
  29.         size--;
  30.     }
  31.     return x;
  32. }
  33.  
  34.  
  35. int isOperand(char x)
  36. {
  37.     if(x == '+' || x == '-' || x == '*' || x == '/' || x == '^') return 0;
  38.     else if((x >= 'a' && x <='z') || (x >= 'A' && x <='Z') || (x >= '0' && x <='9')) return 1;
  39. }
  40.  
  41. int pre(char x)
  42. {
  43.     if(x == '^') return 3;
  44.     if(x == '+' || x == '-') return 1;
  45.     else if(x == '*' || x == '/') return 2;
  46.     else return 0;
  47. }
  48.  
  49. char *convert(char *infix)
  50. {
  51.     char *postfix;
  52.     postfix = (char *) malloc(sizeof(char) * (strlen(infix) + 2));
  53.     int i = 0, j = 0;
  54.     while(infix[i] != '\0')
  55.     {
  56.         if(infix[i] == '(') push(infix[i]);
  57.         if(infix[i] == ')')
  58.         {
  59.             while(a[size] != '(') postfix[j++] = pop();
  60.             pop();
  61.         }
  62.         if(isOperand(infix[i])) postfix[j++] = infix[i++];
  63.         else
  64.         {
  65.             if(pre(infix[i]) > pre(a[size])) push(infix[i++]);
  66.             else postfix[j++] = pop();
  67.         }
  68.     }
  69.     while(size != -1) postfix[j++] = pop();
  70.     postfix[j] = '\0';
  71.     return postfix;
  72. }
  73.  
  74. int main()
  75. {
  76.     char in[1000];
  77.     printf("Enter the infix expression: ");
  78.     scanf("%s", in);
  79.     push('.');
  80.     char *post = convert(in);
  81.    
  82.     printf("The converted postfix expression is: ");
  83.     for(int i = 0; i < strlen(post) - 1; i++) if(post[i] != '(' && post[i] != ')') printf("%c", post[i]);
  84.     printf("\n");
  85. }
  86.  
  87. //k+l-m*n+(o^p)*w/u/v*t+q
  88. //ans: kl+mn*-op^w*u/v/t*+q+
Advertisement
Add Comment
Please, Sign In to add comment