EmbLogic's Blog

Expression Parsing: Infix to postfix

#include<stdio.h>

int top=-1;
char stack[20];
void push(char ch)       //push function()
{
top++;                        // top is incremented
stack[top]=ch;           // character is pushed to stack
}
void pop()                    // pop function()
{
top–;                            // top is decremented
}
int main()
{
char arr[]={‘a’,’+’,’b’,’+’,’(‘,’c’,’*’,’d’,’)’,’+’,’(‘,’e’,’-’,’f’,’)’};          // general expression
int i,j=0,size_arr=sizeof(arr);                                                    // size of array
printf(“%s: Begin\n”,__FILE__);
printf(“%s: size of array is %d\n”,__FILE__,size_arr);
char post_arr[size_arr];                                       // array that saves the final postfix expression
printf(“///////////original expression//////////\n”);
printf(“%s”,arr);
for(i=0;i<size_arr;i++)
{
char ch=arr[i];                                                            // elements of array are one by one assigned to ‘ch’
if(ch==’+’ || ch==’-’ || ch==’*’ || ch==’/’ || ch==’(‘ || ch==’)’)   //ORing between characters
{
if(ch==’)’)                                        // if ‘ch’ is a closing brace
{
while(1)
{
post_arr[j]=stack[top];     // the character at the top of the stack is saved in the postfix array
j++;                                     // index of postfix array is incremented
pop();                                  // pop function called
if(stack[top]==’(‘)            // if top of the stack is an opening brace then pop is again called

{
pop();
break;
}
}
}
else
{
push(ch);     // if ‘ch’ is an operator other than closing brace then push the character in stack
}
}
else
{
post_arr[j]=ch;   // if ‘ch’ is not an operator then push the character in postfix array
j++;
}
}

while(top!=-1)         // when all the characters in original expression are once checked and are present in either stack or postfix array
{
post_arr[j]=stack[top];        // the leftover elements in stack are popped out and saved in postfix array
j++;                                      // index of array is incremented whereas top is decremented
top–;
}

printf(“\n/////////// Postfix expression//////////\n”);
printf(“%s”,post_arr);
printf(“\n%s: End\n”,__FILE__);
return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>