/****************************
* 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;
}
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
Subscribe to:
Posts (Atom)