Monday, January 10, 2011

infix to prefix without bracket

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

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


// the actual algorithm is quiet difficult so doing this simple way

/* OP:
* Enter expression: a*b+d/e
* prefix of entered (infix) expression is:
* +*ab/de
*/


// I will be following the BSD style indentation in all the programs because it feels more readable to me


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

#define MAX 100

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;

char
temp;

int
i, j;

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


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


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


for
(i = 0; c[i] != '\0'; i++) // NULL will give error on iso compiler

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


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

else

{


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


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

PTOP++;
}

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


while
(TOP >= 0)
{

x = pop(s, &TOP);

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

pref[PTOP] = '\0';


//strrev(pref);
// use strrev if it is there in your compiler
// if not available then use following code
i = 0;
j = strlen(pref) - 1;



while
(i < j)
{

temp = pref[i];

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





// now print the reverse of the string
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
'-':
a = 2;
break
;

case
'/':
case
'*':
case
'\\':

case
'%':
a = 5;
break
;

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

break
;
}

return
a;
}

No comments:

Post a Comment