Monday, January 10, 2011

infix to postfix with bracket

/****************************
* Umang B Bhatt *
* bhatt.umang7@gmail.com *
*****************************/

/**
* program for infix to postfix with bracket
*/


#include<stdio.h>
#define MAX 100


/*
* this will not catch errors
* eg if you enter (a*b]+c then it will output ab*c+
*/

/* OP:
* Enter expression: (a*(c+d)+(e+f)*g)/(j+i)
* postfix of entered (infix) expression is:
* acd+*ef+g*+ji+/
*/



// personally, i believe that declaring TOP and S here is bad practice

void
main()
{

int
TOP = -1, PTOP = 0;

char
s[MAX];
char
post[MAX] = {'\0'};

int
pre(char);
int
push(char[], int, char);

int
pop(char *, int *);

char
c[MAX] = {'\0'}, symb, x;

int
i;
printf("Enter expression: ");
gets(c);

/*
* gets will give error when compiling on modern compiler
*/


// x = pop(s,&TOP);
// TOP = push(s,TOP,symb);

for
(i = 0; c[i] != '\0'; i++)
{


symb = c[i];
if
(isalpha(symb) > 0)
{


post[PTOP] = symb;
PTOP++;
}

else if
(symb == '+' || symb == '-' || symb == '*' || symb == '/' || symb == '\\' || symb == '^' || symb == '$')
{


while
((pre(symb)) <= (pre(s[TOP])) && TOP >= 0)
{


x = pop(s, &TOP);
post[PTOP] = x;

PTOP++;
}

TOP = push(s, TOP, symb);
}


else if
(symb == '(' || symb == '[' || symb == '{')
{


TOP = push(s, TOP, symb);
}

else


{

x = '\0';
while
(x != '(' && x != '{' && x != '[')
{


x = pop(s, &TOP);
if
(x != '(' && x != '{' && x != '[')
{


post[PTOP] = x;
PTOP++;
}
}
}
}

while
(TOP >= 0)
{


x = pop(s, &TOP);
post[PTOP] = x;

PTOP++;
}

post[PTOP] = '\0';
printf("\npostfix of entered (infix) expression is:\n%s\n", post);


// getch(); // win not work on linux
}

int
push(char *s, int top, char ele)
{


int
i;
if
(top >= MAX)
{


printf("\nStack Overflow");
}

else

{

s[++top] = ele;
}


return
top;
}


int
pop(char *a, int *top)
{


if
((*top) >= 0)
{
(*
top) = (*top) - 1;

return
a[(*top) + 1];
}

else

{


printf("Stack underflow\n");
return
0;
}
}


int
pre(char x)
{


int
a;
switch
(x)
{

case
'(':

case
'{':
case
'[':
a = -5;

break
;
case
'+':
case
'-':
a = 2;

break
;
case
'/':
case
'*':
case
'\\':

case
'%':
a = 5;
break
;

case
'$':
case
'^':
a = 10;

break
;
}

return
a;
}

No comments:

Post a Comment