DS | Practical-4 | C Program to Convert Infix to Postfix Expression using Stack

on

 

Write a C Program to Convert Infix to Postfix Expression using Stack


GTU DS Practical-4

Implement a program to convert Infix to Postfix notation using Stack.

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<ctype.h>
  4. #include<string.h>
  6. #define SIZE 100
  8. char stack[SIZE];
  9. int top = -1;
  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. }
  24. char pop()
  25. {
  26. char item ;
  28. if(top <0)
  29. {
  30. printf("stack under flow: invalid infix expression");
  31. getchar();
  32. /* underflow may occur for invalid expression */
  33. /* where ( and ) are not matched */
  34. exit(1);
  35. }
  36. else
  37. {
  38. item = stack[top];
  39. top = top-1;
  40. return(item);
  41. }
  42. }
  44. int is_operator(char symbol)
  45. {
  46. if(symbol == '^' || symbol == '*' || symbol == '/' || symbol == '+' || symbol =='-')
  47. {
  48. return 1;
  49. }
  50. else
  51. {
  52. return 0;
  53. }
  54. }
  56. int precedence(char symbol)
  57. {
  58. if(symbol == '^')
  59. {
  60. return(3);
  61. }
  62. else if(symbol == '*' || symbol == '/')
  63. {
  64. return(2);
  65. }
  66. else if(symbol == '+' || symbol == '-')
  67. {
  68. return(1);
  69. }
  70. else
  71. {
  72. return(0);
  73. }
  74. }
  76. void InfixToPostfix(char infix_exp[], char postfix_exp[])
  77. {
  78. int i, j;
  79. char item;
  80. char x;
  82. push('(');
  83. strcat(infix_exp,")");
  85. i=0;
  86. j=0;
  87. item=infix_exp[i];
  89. while(item != '\0')
  90. {
  91. if(item == '(')
  92. {
  93. push(item);
  94. }
  95. else if( isdigit(item) || isalpha(item))
  96. {
  97. postfix_exp[j] = item;
  98. j++;
  99. }
  100. else if(is_operator(item) == 1)
  101. {
  102. x=pop();
  103. while(is_operator(x) == 1 && precedence(x)>= precedence(item))
  104. {
  105. postfix_exp[j] = x;
  106. j++;
  107. x = pop();
  108. }
  109. push(x);
  111. push(item);
  112. }
  113. else if(item == ')')
  114. {
  115. x = pop();
  116. while(x != '(')
  117. {
  118. postfix_exp[j] = x;
  119. j++;
  120. x = pop();
  121. }
  122. }
  123. else
  124. {
  125. printf("\nInvalid infix Expression.\n");
  126. getchar();
  127. exit(1);
  128. }
  129. i++;
  132. item = infix_exp[i];
  133. }
  134. if(top>0)
  135. {
  136. printf("\nInvalid infix Expression.\n");
  137. getchar();
  138. exit(1);
  139. }
  140. if(top>0)
  141. {
  142. printf("\nInvalid infix Expression.\n");
  143. getchar();
  144. exit(1);
  145. }
  147. postfix_exp[j] = '\0';
  149. }
  151. int main()
  152. {
  153. char infix[SIZE], postfix[SIZE];
  155. printf("ASSUMPTION: The infix expression contains single letter variables and single digit constants only.\n");
  156. printf("\nEnter Infix expression : ");
  157. gets(infix);
  159. InfixToPostfix(infix,postfix);
  160. printf("Postfix Expression: ");
  161. puts(postfix);
  163. return 0;
  164. }

Output:




Go To :

Home Page :

Practical-3 :

Practical-5 :

Comments

Post a Comment