Infix to postfix using stack: infix, postfix, and prefix are the different notations to solve the expressions. we use the stack to Convert infix expression to postfix expression in C.
Infix expression: Infix expression is the expression that contains the operator between two operands.
Example: A+B
Postfix expression: Postfix expression is the expression that contains operands first and then the operator which performs on that operands.
Example: AB+

Infix to postfix example
Convert the following infix expression to postfix expression.
Infix expression: A+B*C
Postfix expression: ABC*+

Infix to postfix algorithm

  1. Create a stack
  2. for each character ‘t’ in the input stream {
    if (t is an operand)
    output t
    else if (t is a right parenthesis){
    POP and output tokens until a left parenthesis is popped(but do not output)
    }
    else {
    POP and output tokens until one of lower priority than t is encountered or a left parenthesis is encountered
    or the stack is empty
    PUSH t
    }
  3. POP and output tokens until the stack is empty

Program to convert infix to postfix using stack

#define SIZE 50
#include <ctype.h>
char s[SIZE];
int top=-1; /* Global declarations */

push(char elem)
{ /* Function for PUSH operation */
s[++top]=elem;
}

char pop()
{ /* Function for POP operation */
return(s[top--]);
}

int pr(char elem)
{ /* Function for precedence */
switch(elem)
{
case '#': return 0;
case '(': return 1;
case '+':
case '-': return 2;
case '*':
case '/': return 3;
}
}

main()
{ /* Main Program */
char infix[50],postfix[50],ch,elem;
int i=0,k=0;
printf("\n\nEnter Infix Expression : ");
scanf("%s",infix);
push('#');
while( (ch=infix[i++]) != '
#define SIZE 50
#include <ctype.h>
char s[SIZE];
int top=-1; /* Global declarations */

push(char elem)
{ /* Function for PUSH operation */
s[++top]=elem;
}

char pop()
{ /* Function for POP operation */
return(s[top--]);
}

int pr(char elem)
{ /* Function for precedence */
switch(elem)
{
case '#': return 0;
case '(': return 1;
case '+':
case '-': return 2;
case '*':
case '/': return 3;
}
}

main()
{ /* Main Program */
char infix[50],postfix[50],ch,elem;
int i=0,k=0;
printf("\n\nEnter Infix Expression : ");
scanf("%s",infix);
push('#');
while( (ch=infix[i++]) != '\0')
{
if( ch == '(') push(ch);
else
if(isalnum(ch)) postfix[k++]=ch;
else
if( ch == ')')
{
while( s[top] != '(')
postfix[k++]=pop();
elem=pop(); /* Remove ( */
}
else
{ /* Operator */
while( pr(s[top]) >= pr(ch) )
postfix[k++]=pop();
push(ch);
}
}
while( s[top] != '#') /* Pop from stack till empty */
postfix[k++]=pop();
postfix[k]='\0'; /* Make postfix as valid string */
printf("\nPostfix Expression = %s\n",postfix);
}
') { if( ch == '(') push(ch); else if(isalnum(ch)) postfix[k++]=ch; else if( ch == ')') { while( s[top] != '(') postfix[k++]=pop(); elem=pop(); /* Remove ( */ } else { /* Operator */ while( pr(s[top]) >= pr(ch) ) postfix[k++]=pop(); push(ch); } } while( s[top] != '#') /* Pop from stack till empty */ postfix[k++]=pop(); postfix[k]='
#define SIZE 50
#include <ctype.h>
char s[SIZE];
int top=-1; /* Global declarations */

push(char elem)
{ /* Function for PUSH operation */
s[++top]=elem;
}

char pop()
{ /* Function for POP operation */
return(s[top--]);
}

int pr(char elem)
{ /* Function for precedence */
switch(elem)
{
case '#': return 0;
case '(': return 1;
case '+':
case '-': return 2;
case '*':
case '/': return 3;
}
}

main()
{ /* Main Program */
char infix[50],postfix[50],ch,elem;
int i=0,k=0;
printf("\n\nEnter Infix Expression : ");
scanf("%s",infix);
push('#');
while( (ch=infix[i++]) != '\0')
{
if( ch == '(') push(ch);
else
if(isalnum(ch)) postfix[k++]=ch;
else
if( ch == ')')
{
while( s[top] != '(')
postfix[k++]=pop();
elem=pop(); /* Remove ( */
}
else
{ /* Operator */
while( pr(s[top]) >= pr(ch) )
postfix[k++]=pop();
push(ch);
}
}
while( s[top] != '#') /* Pop from stack till empty */
postfix[k++]=pop();
postfix[k]='\0'; /* Make postfix as valid string */
printf("\nPostfix Expression = %s\n",postfix);
}
'; /* Make postfix as valid string */ printf("\nPostfix Expression = %s\n",postfix); }

Output:

Infix to postfix using stack

Write A Comment