Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   "Infix-Postfix" & "Postfix-Infix" codes problem (http://www.go4expert.com/forums/infix-postfix-postfix-infix-codes-t14495/)

SHENGTON 11Oct2008 09:32

"Infix-Postfix" & "Postfix-Infix" codes problem
 
Good day Go4Expert experts.

This is my first post here and hope you can help me with my problem. I'm a noob with Borand C++.

I see a tutorial here "Converting and Evaluating Infix, Postfix and Prefix Expressions in C". I copied the code and run it in my Borland C++ program.

Problem with "Infix to Postfix"
Here's what I get if I run the code:

http://i168.photobucket.com/albums/u...xtoPostfix.jpg

I'll just include the code here:
Code:

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

#define MAX 10
#define EMPTY -1

struct stack
{
        char data[MAX];
        int top;
};

int isempty(struct stack *s)
{
        return (s->top == EMPTY) ? 1 : 0;
}

void emptystack(struct stack* s)
{
        s->top=EMPTY;
}

void push(struct stack* s,int item)
{
        if(s->top == (MAX-1))
        {
                printf("\nSTACK FULL");
        }
        else
        {
                ++s->top;
                s->data[s->top]=item;
        }
}

char pop(struct stack* s)
{
        char ret=(char)EMPTY;
        if(!isempty(s))
        {
                ret= s->data[s->top];
                --s->top;
        }
        return ret;
}

void display(struct stack s)
{
        while(s.top != EMPTY)
        {
                printf("\n%d",s.data[s.top]);
                s.top--;
        }
}

int isoperator(char e)
{
        if(e == '+' || e == '-' || e == '*' || e == '/' || e == '%')
                return 1;
        else
                return 0;
}


int priority(char e)
{
        int pri = 0;

        if(e == '*' || e == '/' || e =='%')
                pri = 2;
        else
        {
                if(e == '+' || e == '-')
                        pri = 1;
        }
        return pri;
}

void infix2postfix(char* infix, char * postfix, int insertspace)
{
        char *i,*p;
        struct stack X;
        char n1;
        emptystack(&X);
        i = &infix[0];
        p = &postfix[0];

        while(*i)
        {
                while(*i == ' ' || *i == '\t')
                {
                        i++;
                }

                if( isdigit(*i) || isalpha(*i) )
                {
                        while( isdigit(*i) || isalpha(*i))
                        {
                                *p = *i;
                                p++;
                                i++;
                        }
                        /*SPACE CODE*/
                        if(insertspace)
                        {
                                *p = ' ';
                                p++;
                        }
                        /*END SPACE CODE*/
                }

                if( *i == '(' )
                {
                        push(&X,*i);
                        i++;
                }

                if( *i == ')')
                {
                        n1 = pop(&X);
                        while( n1 != '(' )
                        {
                                *p = n1;
                                p++;
                                /*SPACE CODE*/
                                if(insertspace)
                                {
                                        *p = ' ';
                                        p++;
                                }
                                /*END SPACE CODE*/
                                n1 = pop(&X);
                        }
                        i++;
                }

                if( isoperator(*i) )
                {
                        if(isempty(&X))
                                push(&X,*i);
                        else
                        {
                                n1 = pop(&X);
                                while(priority(n1) >= priority(*i))
                                {
                                        *p = n1;
                                        p++;
                                        /*SPACE CODE*/
                                        if(insertspace)
                                        {
                                                *p = ' ';
                                                p++;
                                        }
                                        /*END SPACE CODE*/
                                        n1 = pop(&X);
                                }
                                push(&X,n1);
                                push(&X,*i);
                        }
                        i++;
                }
        }
        while(!isempty(&X))
        {
                n1 = pop(&X);
                *p = n1;
                p++;
                /*SPACE CODE*/
                if(insertspace)
                {
                        *p = ' ';
                        p++;
                }
                /*END SPACE CODE*/
        }
        *p = '\0';
}

int main()
{
        char in[50],post[50];

        strcpy(&post[0],"");
        printf("Enter Infix Expression : ");
        fflush(stdin);
        gets(in);
        infix2postfix(&in[0],&post[0],1);
        printf("Postfix Expression is : %s\n",&post[0]);

        return 0;
}
/* SAMPLE OUTPUT:
Enter Infix Expression : A + B + C / (E - F)
Postfix Expression is : A B + C E F - / + 
*/


Problem with "Postfix to Infix"
Here's the code of Postfix to Infix conversion:
Code:

/* include necessary preprocessor header files */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

/* constants */
#define TRUE 1
#define FALSE 0

/* structure for stack */
typedef struct
{
char data[20]; /* array to hold stack contents */
int tos; /* top of the stack pointer */
} STACK;


/* function prototypes */
void initStack(STACK *stack);
void get_postfix(char infix[]);
void convertToinfix(char postfix[], char infix[]);
int isOperator(char c);
int precedence(char operator1, char operator2);
int pred_level(char ch);
void push(STACK *stack, char value);
char pop(STACK *stack);
char stackTop(STACK *stack);
int isEmpty(STACK *stack);
int isFull(STACK *stack);
void printResult(char postfix[], char infix[]);
void print_msg(void);


int main(void)
{
char postfix[20], infix[20] ="";
//float result;

/* convert from infix to postfix main function */
convertToinfix(postfix, infix);

/* display the infix equivalent */
infix[strlen(postfix)-2] = '\0';
printResult(postfix, infix /*, result*/);

return EXIT_SUCCESS;
}

void initStack(STACK *stack)
{
stack->tos = -1; /* stack is initially empty */
}


void get_postfix(char postfix[])
{
int i;

printf("Enter postfix expression below (max 18 characters excluding spaces) : \n");
fflush(stdin);
/* to read in only 18 characters excluding spaces */
for ( i=0; i<18; )
{
if ( (postfix[i] = getchar()) == '\n' )
{
i++;
break;
}
else if ( !(isspace(postfix[i])) )
i++;
}

postfix[i] = '\0';
}

void convertToinfix(char postfix[], char infix[])
{
int i, length;
int j=0;
char tos_ch;
STACK stack;

initStack(&stack); /* initialise stack */
get_postfix(postfix); /* get postfix expression from user */
length = strlen(postfix);

/* if strlen if postfix is more than zero */
if ( length )
{
push(&stack, '(');
strcat(postfix, ")");
length++;

for ( i=0; i<length; i++ )
{
/* if current operator in postfix is digit */
if ( isdigit(postfix[i]) )
{
infix[j++] = postfix[i];
}
/* if current operator in postfix is left parenthesis */
else if ( postfix[i] == '(' )
{
push(&stack, '(');
}
/* if current operator in postfix is operator */
else if ( isOperator(postfix[i]) )
{
while ( TRUE )
{
/* get tos */
tos_ch = stackTop(&stack);

/* no stack left */
if ( tos_ch == '\0' )
{
printf("\nInvalid postfix expression\n");
print_msg();
exit(1);
}
else
{
if ( isOperator(tos_ch) )
{
if ( pred_level(tos_ch) >= pred_level(postfix[i]) )
infix[j++] = pop(&stack);
else
break;
}
else
break;
}
}
push(&stack, postfix[i]);
}
/* if current operator in postfix is right parenthesis */
else if ( postfix[i] == ')' )
{
while ( TRUE )
{
/* get tos */
tos_ch = stackTop(&stack);

/* no stack left */
if ( tos_ch == '\0' )
{
printf("\nInvalid postfix expression\n");
print_msg();
exit(1);
}
else
{
if ( tos_ch != '(' )
{
infix[j++] = tos_ch;
pop(&stack);
}
else
{
pop(&stack);
break;
}
}
}
continue;
}
}
}

infix[j] = '\0';
}


/* determine if c is an operator */
int isOperator(char c)
{
if ( c == '+' || c == '-' || c == '*' ||
c == '/' || c == '%' || c == '^' )
{
return TRUE;
}
else
return FALSE;
}

/* determine precedence level */
int pred_level(char ch)
{
if ( ch == '+' || ch == '-' )
return 1;
else if ( ch == '^' )
return 3;
else
return 2;
}

/* determine if the precedence of operator1 is less than,
equal to, greater than the precedence of operator2 */
int precedence(char operator1, char operator2)
{
if ( pred_level(operator1) > pred_level(operator2) )
return 1;
else if ( pred_level(operator1) < pred_level(operator2) )
return -1;
else
return 0;
}

/* push a value on the stack */
void push(STACK *stack, char value)
{
if ( !(isFull(stack)) )
{
(stack->tos)++;
stack->data[stack->tos] = value;
}
}

/* pop a value off the stack */
char pop(STACK *stack)
{
char ch;

if ( !(isEmpty(stack)) )
{
ch = stack->data[stack->tos];
(stack->tos)--;
return ch;
}
else
return '\0';
}

/* return the top value of the stack without popping the stack */
char stackTop(STACK *stack)
{
if ( !(isEmpty(stack)) )
return stack->data[stack->tos];
else
return '\0';
}

/* determine if stack is empty */
int isEmpty(STACK *stack)
{
/* empty */
if ( stack->tos == -1 )
return TRUE;
/* not empty */
else
return FALSE;
}

/* determine if stack is full */
int isFull(STACK *stack)
{
/* full */
if ( stack->tos == 19 )
return TRUE;
/* not full */
else
return FALSE;
}


/* display the result postfix expression */
void printResult(char postfix[], char infix[]/*, float result*/)
{
/*system("cls");*/
printf("\n\n");
printf("Postfix notation: %s\n\n", postfix);
printf("Infix notation : %s\n", infix);
//printf("Result is: %f\n", result);
print_msg();
}

/* print exit message */
void print_msg(void)
{
printf("Hit <RETURN> to exit......");
fflush(stdin);
getchar();
}

When I run this code this what I get:
http://i168.photobucket.com/albums/u...ixtoInfix1.jpg

When I press enter this is the result:
http://i168.photobucket.com/albums/u...ixtoInfix2.jpg

What's wrong with the code?

I'm just a beginner with Borland C++. Hope you can help me with this Gurus.

Thanks and God bless. :)

shabbir 11Oct2008 09:53

Re: "Infix-Postfix" & "Postfix-Infix" codes problem
 
Refer to InFix to PostFix and PostFix expression evaluation. written by me which I think would help you solve your problem

SHENGTON 11Oct2008 12:00

Re: "Infix-Postfix" & "Postfix-Infix" codes problem
 
Thanks for your code Sir shabbir. It really helps. However, how about the Infix to Postfix above? What's wrong with the code?

I'm just a beginner Sir, hope you can help me.

Thanks and God bless. :)

shabbir 11Oct2008 13:01

Re: "Infix-Postfix" & "Postfix-Infix" codes problem
 
Thats pretty simple code where you just arrange the postfix expression in binary tree and Inorder traversal gives you infix expression. I don't have the ready code as of now but I guess it would not be that difficult to write as well for you if you have the concept and one part of it

SHENGTON 12Oct2008 14:17

Re: "Infix-Postfix" & "Postfix-Infix" codes problem
 
Thanks Sir.


All times are GMT +5.5. The time now is 01:17.