Showing posts with label infix to prefix with bracket. Show all posts
Showing posts with label infix to prefix with bracket. Show all posts

Monday, January 10, 2011

infix to prefix with bracket

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

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


#include<stdio.h>
#include<string.h>

#define MAX 100

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


/* OP:
* Enter expression: (a*(c+d)+(e+f)*g)/(j+i)
* prefix of entered (infix) expression is:
* /+*a+cd*+efg+ji
*
*/




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

void
main()
{

int
TOP = -1, PTOP = 0;

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

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

int
pop(char *, int *);

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

int
i, j;
char
temp;
printf("Enter expression: ");

gets(c);

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


/*
* here i don't have strrev function on my compiler (gcc) so i am doing this manually
* but you can write strrev(c); if your compiler supports it
*/

i = 0;

j = strlen(c) - 1;
while
(i < j)
{


temp = c[i];
c[i++] = c[j];

c[j--] = temp;
}


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

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


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


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

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


while
((pre(symb)) < (pre(s[TOP])))
{


x = pop(s, &TOP);
pref[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 != ')')
{


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

while
(TOP >= 0)
{


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

PTOP++;
}

pref[PTOP] = '\0';




i = 0;
j = strlen(pref) - 1;


while
(i < j)
{

temp = pref[i];

pref[i++] = pref[j];
pref[j--] = temp;
}




printf("\nprefix of entered (infix) expression is:\n%s\n", pref);


// 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;
}