Infix to Postfix using stack in C <incorrect output after a '(' is inserted in the expression>

Question

#include<stdio.h>
#include<stdlib.h>
#define MAX 100

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

void push(stack*,char);
char pop(stack*);
int empty(stack*);
int priority(char);
char top(stack*);

int main(int argc,char* argv[])
{
    stack s;
    char ch,token,temp,temp1;
    int k=0;
    char infix[MAX];
    s.top=-1;

    printf("\nInput an infix expression.\n");
    scanf("%s",infix);
    while((ch=infix[k++])!='\0')
    {
        if(isalnum(ch)) // checks if character is alphanumeric
            printf("%c",ch);
        else if(ch=='(') // if '(' push to stack
            push(&s,ch);
        else if(ch==')')  // if ')' pop all elements till a '(' is encountered 
            while(token=pop(&s)!='(')
            {
                printf("%c",token);
            }
        else
        {
            // if character is an operator
            while(!empty(&s) && priority(ch)<=priority(top(&s))) 
            {
                token=pop(&s);
                printf("%c",token);
            }
            push(&s,ch);
        }
    }

    if(!empty(&s)) // prints the remaining characters in the stack
    {
        token=pop(&s);
        printf("%c",token);
    }

    return 0;
}

void push(stack* s,char ch)
{
    if(s->top==-1)
        s->top=0;
    else
        s->top=s->top+1;
    s->data[s->top]=ch;
}

char pop(stack* s)
{
    char ch;
    ch=s->data[s->top];
    s->top=s->top-1;
    return ch;
}

int empty(stack* s)
{
    if(s->top==-1)
        return 1;
    return 0;
}

int priority(char ch)
{
    if(ch=='(')
        return 1;
    else if(ch=='+' || ch=='-')
        return 2;
    else if(ch=='*' || ch=='/' || ch=='%')
        return 3;
}

char top(stack* s)
{
    return (s->data[s->top]);
}

OUTPUT

Input an infix expression.

(a+b)*c/(a+b*c)

ab☺c*abc☺☺/

Input an infix expression.

a+b-c/d

ab+cd/

The program displays invalid characters when a '(' is inserted. Your help would be greatly appreciated.

Answer 1

if(isalnum(ch))

You should #include <ctype.h> if you use isalnum.

while(token=pop(&s)!='(')

The comparison operators have precedence over the assignment operator, which means that here you are comparing pop(&s)!='(' and then assign the result (0 or 1) to token. The comparison will still work and the loop behave correctly, but the character in token will be some control character, rather than a letter.

Use correct parentheses:

while((token=pop(&s))!='(')

Your function int priority(char ch) does not have a return statement for every possible input. You should add a final return statement to catch these cases (even if they should not happen)

Also much of your code is too verbose without need. For example:

char pop(stack* s)
{
    char ch;
    ch=s->data[s->top];
    s->top=s->top-1;
    return ch;
}

is the same as:

char pop(stack* s)
{
    s->top--;
    return s->data[s->top+1];
}

or

int empty(stack* s)
{
    if(s->top==-1)
        return 1;
    return 0;
}

is the same as

int empty(stack* s)
{
    return s->top == -1;
}

Answer 2

Precedence. The assignment operator has a very low precedence, so

while(token=pop(&s)!='(')

behaves like so:

while (token = (pop(&s)!='(') )

and token is only assigned 1 or 0 depending on the result of the comparison. You want:

while ((token=pop(&s)) != '(')