Turbo C - InFix to PostFix Conversion
I have given here the source code in Turbo C for InFix to PostFix Conversion with the help of Stack (Last In First Out) implementation. For dynamic memory allocation, I have used malloc, realloc and free functions.
Source Code
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _MyStack
{
char *m_data;
int m_numElements;
} MyStack;
int push(MyStack *s, char chData)
{
if(s->m_data == NULL) // root node
{
s->m_numElements = 1;
s->m_data = (char*) malloc(sizeof(char));
}
else
{
s->m_numElements++;
s->m_data = (char*)realloc(s->m_data, s->m_numElements * sizeof(char));
memmove(&s->m_data[1], s->m_data, (s->m_numElements - 1) * sizeof(char));
}
s->m_data[0] = chData;
return 1;
}
int pop(MyStack *s)
{
if(s->m_data == NULL) // root node
{
s->m_numElements = 0;
return 0;
}
else
{
if(s->m_numElements == 1)
{
// last item
s->m_numElements = 0;
free(s->m_data);
s->m_data = NULL;
return 0;
}
else
{
s->m_numElements--;
memmove(s->m_data, &s->m_data[1], s->m_numElements * sizeof(char));
s->m_data = (char*) realloc(s->m_data, s->m_numElements * sizeof(char));
}
}
return 1;
}
char top(MyStack *s)
{
if(s->m_numElements > 0)
return s->m_data[0];
return 0;
}
int size(MyStack *s)
{
return s->m_numElements;
}
int main(int argc, char *argv[])
{
MyStack *s1 = (MyStack *)malloc(sizeof(MyStack));
int sz, i, j, len, priority;
char infix[512], postfix[512];
char *p = infix;
int postfixlen = 0;
memset(postfix, 0, sizeof(postfix));
memset((void*)s1, 0, sizeof(MyStack));
if(argc != 2)
{
printf("Usage: InFixCnv.exe <infix expression>\n");
exit(0);
}
strcpy(infix, argv[1]);
while(1)
{
if(p == 0 || *p == '\0')
{
len = size(s1);
if(len <= 0)
break;
else for(j = 0; j < len; j++)
{
postfix[postfixlen++] = top(s1);
pop(s1);
}
}
if(*p == '+' || *p == '-' || *p == '*' || *p == '/')
{
// check the precedence
if(size(s1) <= 0)
push(s1, *p);
else
{
if( top(s1) == '*' || top(s1) == '/')
priority = 1;
else
priority = 0;
if(priority == 1)
{
if(*p == '+' || *p == '-')
{
postfix[postfixlen++] = top(s1);
pop(s1);
p--;
}
else
{
postfix[postfixlen++] = top(s1);
pop(s1);
p--;
}
}
else
{
if(*p == '+' || *p == '-')
{
postfix[postfixlen++] = top(s1);
pop(s1);
push(s1, *p);
}
else
push(s1, *p);
}
}
}
else
{
postfix[postfixlen++] = *p;
}
p++;
}
printf("InFix :\t%s\n", infix);
printf("PostFix:\t%s\n", postfix);
return 0;
}
Click here to download Turbo C Source Code and Executable
Output
InFix : a+b*c
PostFix: abc*+
InFix : a+b*c/d-e
PostFix: abc*d/+e-
InFix : a+b*c/d-e+f*h/i+j-k
PostFix: abc*d/+e-fh*i/+j+k-
Press any key to continue . . .
|
|