C Program to convert a valid Infix expression to postfix using Structures
Program
#include<stdio.h>
#include<ctype.h>
#define STACK_SIZE 50
#define LENGTH 50
struct stack
{
char data[LENGTH];
int top;
};
typedef struct stack STACK;
int isFull(STACK st)
{
return (st.top == STACK_SIZE -1) ? 1 : 0;
}
int isEmpty(STACK st)
{
return (st.top == -1) ? 1 : 0;
}
void push(char item, STACK *st)
{
if(isFull(*st))
{
printf("Stack overflow!!!\n");
return;
}
st->top++;
st->data[st->top] = item;
}
char pop(STACK *st)
{
char item_deleted;
if(isEmpty(*st))
{
printf("Stack underflow!!!\n");
return 0;
}
item_deleted = st->data[st->top];
st->top--;
return item_deleted;
}
int priority(char symbol)
{
switch(symbol)
{
case '#': return 0;
case '(': return 1;
case '+':
case '-': return 2;
case '*':
case '/': return 3;
case '$':
case '^': return 4;
}
}
void infix_to_postfix(char infix[], char postfix[])
{
STACK st;
char symbol;
int i, j;
st.top = -1;
push('#', &st);
j = 0;
while((symbol = infix[i++]) != '\0')
{
if(symbol == '(')
push(symbol, &st);
else if(isalnum(symbol))
postfix[j++] = symbol;
else if(symbol == ')')
{
while(st.data[st.top] != '(')
postfix[j++] = pop(&st);
pop(&st);
}
else
{
while(priority(st.data[st.top]) >= priority(symbol))
postfix[j++] = pop(&st);
push(symbol, &st);
}
}
while(st.data[st.top] != '#')
postfix[j++] = pop(&st);
postfix[j] = '\0';
}
void main()
{
char infix[LENGTH], postfix[LENGTH];
printf("Enter a valid infix expression\n");
scanf("%s", infix);
infix_to_postfix(infix, postfix);
printf("Given Infix expression:\t%s\n", infix);
printf("Converted Postfix expression:\t%s\n", postfix);
}
Output
Enter a valid infix expression
A*(B-C)+D+(E/F)$G
Given Infix expression: A*(B-C)+D+(E/F)$G
Converted Postfix expression: ABC-*D+EF/G$+