Return value of a function in C

Question

I tried writing some code to check if the paranthesis in an expression are balances using the below function. Can someone help me understand why the below function is returning 1 in case of a balanced expression when it's not specified anywhere to return 1.

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

struct Stack
{
    int top;
    unsigned capacity;
    char* array;
};

struct Stack* createStack (unsigned capacity)
{
    struct Stack* stack = (struct Stack*) malloc (sizeof(struct Stack));
    if(!stack)
        return NULL;

stack->top = -1;
stack->capacity = capacity;
stack->array = (char*) malloc(stack->capacity * sizeof(int));

if (!stack->array)
    return NULL;
return stack;
}

int isEmpty(struct Stack* stack)
{
    return (stack->top == -1);
}
void push(struct Stack* stack, char op)
{
    stack->top++;
    stack->array[stack->top] = op;

}

int pop(struct Stack* stack)
{

    if (!isEmpty(stack))
        return (stack->array[stack->top--]);
    return '$';
}

int isMatchingPair(char char1 , char char2)
{
    if (char1 == '(' && char2 == ')')
        return 1;
    else if (char1 == '[' && char2 == ']')
        return 1;
    else if (char1 == '{' && char2 == '}')
        return 1;
    else
        return 0;
}

int paranthesesMatch(char* exp)
{
    int i;
    struct Stack* stack = createStack(strlen(exp));
    for(i = 0; exp[i]; i++)
    {
        if (exp[i] == '(' || exp[i] == '[' || exp[i] == '{')
        push(stack , exp[i]);
       if (exp[i] == ')' || exp[i] == ']' || exp[i] == '}')
       {
        if (stack == NULL)
            return 0;
        else if ( !isMatchingPair(pop(stack), exp[i]) )
           return 0;

       }
    }
}

int main()
{
  char exp[100] = "{()}[)";
  printf(" %d\n", paranthesesMatch(exp));
  if (paranthesesMatch(exp) == 1)
    printf("Balanced \n");
  else
    printf("Not Balanced \n");  
   return 0;
}  

Edit: Added the full code.

Answer 1

why the below function is returning 1 in case of a balanced expression when it's not specified anywhere to return 1.

Your function has branches of code that do not return a value at all. Specifically, when the loop reaches the end, your function does not specify what to return. In situations like that using function's return value is undefined behavior: whatever the function appears to "return" is a junk left-over value that could be different on different computers, or even on the same computer when you run the program multiple times.

As far as the function itself goes, the NULL check for a stack is probably incorrect, unless the code deletes the stack once it's empty (which would be a rather poor decision). In addition, the code has a memory leak, because stack is never freed. It also over-allocates stack->array content by a factor of sizeof(int) (4 on many computers these days):

stack->array = (char*) malloc(stack->capacity * sizeof(int));

should be

stack->array = malloc(stack->capacity);

because you make a stack of chars, not a stack of ints.

Finally, there is no need to allocate stack dynamically. Allocate an array of chars, and make a "stack pointer" or stack index to point at the beginning of your stack. Increment and decrement the pointer/index when you push/pop elements onto the stack. If you use a variable-length array, you wouldn't need to clean up dynamically allocated memory.

Answer 2

Your function returning 1 is the result of undefined behavior. The compiler is free to do whatever it desires, because not all execution paths in your function yield a return statement.

The reason it may appear to work is that the caller (that is unaware that the function finished without a return statement), tries to access the returned value (which may be in a designated register). And your function modifies said register before returning to the caller.

Bumping up your warning levels when building, will produce a diagnostic about it (like so). You should consider promoting that particular warning to an error, since omitting a return statement can result in sinister and hard to find bugs.

Answer 3

Ah as reference to this remember this.. Flowing off the end of a function is same as a return with no expression. In either of this case, the return value is undefined.