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

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