Balanced expression checker

Question

This program detects whether an expression is balanced or not. I would like to know how I can make this more efficient.

#include<stdio.h>
#include<stdlib.h>

struct Stack{
char data;
struct Stack *next;
};

void push(struct Stack **top,char data)
{
        struct Stack *new_node;
        new_node=malloc(sizeof(struct Stack));
        new_node->data=data;
        new_node->next=*top;
        *top=new_node;
}
int compare(char str,char op)
{
        if( (op == '(' && str == ')') || (op == '{' && str == '}') || (op == '[' && str == ']') || (op == '<' && str == '>') )
                return 1;
        else
                return 0;
}
int pop(struct Stack **top,char str)
{
        char op,ret;
        struct Stack *temp=*top;
        if(*top==NULL)
                return 0;

        else if(*top!=NULL)
        {
                // Pop the element and then call comapre function
                op=(*top)->data;
                free(temp);
                *top=(*top)->next;
                return(ret=compare(str,op));
        }
return 1;
}
void display(struct Stack *top)
{
        struct Stack *temp=top;
        while(temp!=NULL)
        {
                printf("%c ",temp->data);
                temp=temp->next;
        }
printf("\n");
}
int isNotEmpty(struct Stack *top)
{

        if(top!=NULL)
                return 1;
        else
                return 0;
}
int main(void)
{
        struct Stack *top=NULL;
        int i=0,y,flag=0;
        char str[]="((A+B)+(C+D)>";
        printf("\n Running the programe to check if the string is balanced or not ");
        for(i=0;str[i]!='\0';++i)
        {
                if( str[i] == '(' || str[i] == '[' || str[i] == '{' || str[i] == '<' )
                        push(&top,str[i]);
                else if( str[i] == ')' || str[i] == ']' || str[i] == '}' || str[i] == '>')
                {
                        y=pop(&top,str[i]);
                        if(!y)
                        {
                                printf("\n Unbalanced Expression ");
                                flag=1;
                        }
                }
        }
        if(!flag)
        {
                if(isNotEmpty(top))
                        printf(" \nUnbalanced Expression ");
                else
                        printf(" \n Balanced Expression ");
        }
        printf("\n");
        return 0;
}

Answer 1

pop() function

For this review, I'll only look at the pop() function, as it is representative of the whole program:

int pop(struct Stack **top,char str)
{
        char op,ret;
        struct Stack *temp=*top;
        if(*top==NULL)
                return 0;

        else if(*top!=NULL)
        {
                // Pop the element and then call comapre function
                op=(*top)->data;
                free(temp);
                *top=(*top)->next;
                return(ret=compare(str,op));
        }
return 1;
}

Purpose of the function

The first thing is that the function doing more than what its name says. Not only is it popping an element off the stack, it is also trying to determine the correctness of the close brace with the open brace. Ideally, your pop function should just pop an element off the stack and let the caller do the rest. It's not a good idea to combine multiple unrelated tasks into single functions.

Naming

I don't particularly like top as the name of your stack but I can live with it. But str is a terrible name for a character. Anyone who reads your code will think that str is a string. Especially because in main you have a string named str. I don't really like op either. What does it mean?

Useless variable

The variable ret is useless and can be removed.

Useless statements

The else condition is always true and can be removed. The return 1 at the end can never be reached and can be removed.

Use of freed variable

You call free() before you set the stack to the next element, which is a mistake. You are actually reading the next pointer from memory that is already freed. You should reverse the order of those two statements.

Indentation

Your indentation is a bit strange with the return 1 unindented.

Rewrite

If you want to keep it in one function:

int popAndCompare(struct Stack **pStack, char closeBrace)
{
    struct Stack *top = *pStack;
    char openBrace;

    if (top == NULL)
        return 0;

    // Pop the element and then call compare function
    *pStack   = top->next;
    openBrace = top->data;
    free(top);
    return compare(closeBrace, openBrace);
}

Otherwise, separate the tasks:

char pop(struct Stack **pStack)
{
    struct Stack *top = *pStack;
    char ret;

    if (top == NULL)
        return '\0';

    *pStack = top->next;
    ret     = top->data;
    free(top);
    return ret;
}

int main(void)
{
    // ...
            char openBrace = pop(&stack);
            if (!compare(str[i], openBrace)
            {
                printf("\n Unbalanced Expression ");
                flag=1;
            }
    // ...
}

Answer 2

compare() function

int compare(char str,char op)
 {
       if( (op == '(' && str == ')') || (op == '{' && str == '}') || (op == '[' && str == ']') || (op == '<' && str == '>') )
              return 1;
       else
              return 0;
}   

There are many improvements to be made.

• The return type should be bool not int for better logical clarity. (C99 is required).

• This kind of IF statement can be omitted completely.

• You should separate the bool expression on more lines.

• compare is a terrible name, it is so general it does not give information, I suggest are_opening_and_closing

• The argument names are terrible, str is intended to be multichar and op is one of *-/+. I suggest maybe_opening maybe_closing

Answer 3

As you are asking about efficiency:

Your algorithm is:
Check character for all variants of the opening brace
Push that character
Check character for all variants of the closing brace
Pop the character and compare all valid combinations

I would just push the expected order of closing braces, if the focus is maximum efficiency. Assuming a pop() that only pops:

char getClosingBrace(char openingBrace)
{
  switch(openingBrace)
  {
    case '{':
      return '}';
    case '(':
      return ')';
    case '<':
     return '>';
    case '[';
     return ']';
    default:
     return 0;
  }
}


bool isClosingBrace(char brace)
{
  switch(brace)
  {
    case '}':
    case ']':
    case ')':
    case '>':
      return true;
    default:
      return false;  
  }
}

...

char closingBrace;

if(closingBrace = getClosingBrace(str[i])) push(&top, closingBrace);
else if(isClosingBrace(str[i]))
{
  closingBrace = pop(&top);
  if(closingBrace != str[i]) flag = 1;
}

This way you sacrifice maybe readability, but save 1/3 of the comparisons.