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

struct stack {
    int size;
    int top;
    char *arr;
};

void push(struct stack *st,char x) {
    if (st->top >= st->size - 1) {
        printf("stack is full");
    }
    else {
        st->top  ;
        st->arr[st->top] = x;
    }
}

char pop(struct stack *st) {
    char x;

    if (st->top < 0) {
        printf("stack is empty");
    }
    else {
        x = st->arr[st->top];
        st->top--;
    }

    return x;
}

int isempty(struct stack st) {
    if (st.top < 0) {
        return 1;
    }
    else
        return 0;
}

void display(struct stack st) {
    int i;
    for (i = st.top; i >= 0; i--) {
        printf("%c ", st.arr[i]);
    }

    printf("\n");
}

int balanced(char *expr) {
    int i;
    struct stack st;
    st.size = strlen(expr);
    st.top = -1;
    st.arr = (char *)malloc(st.size * sizeof(char));
    
    for (i = 0; expr[i] != '\0'; i  ) {
        if (expr[i] = '(') {
            push(&st, expr[i]);
        }
        else if (expr[i] = ')') {
            if (st.top < 0) return false;
            else pop(&st);
        }
    }

    if (st.top < 0) return 1;
    else return 0;
}

int main() {
    char *expr = "((a b))";
    printf("%d", balanced(expr));

    return 0;
}

Paranthesis matching using stack implemented in array in c programming .Nothing gets printed when I call the balanced() function.How to correct the above code? Apart from this method is there any other way to check paranthesis matching and checking if the expression is valid too i.e; (a )b In this paranthesis is balanced but expression is not valid

CodePudding user response：

In this loop:

   for (i = 0; expr[i] != '\0'; i  ) {
       if (expr[i] = '(') {
           push(&st, expr[i]);
       }
       else if (expr[i] = ')') {
           if (st.top < 0) return false;
           else pop(&st);
       }
   }

You have assignments, rather than checks for equality. = vs. ==.

The first condition is always true, so every character is made '(' and pushed onto the stack. Nothing is ever popped from the stack.

You also need to include <stdbool.h> if you wish to use true and false.

Correcting those issues and running the program, the output is 1.

CodePudding user response：

Others have noted the assignment that should have been test for equality.

While it's interesting to use a stack, you could also simply have used a signed integer counter initialised to zero. Increment when encountering an '(' and decrement when encountering a ')'. If the counter goes negative, or a positive final value is found, then the parentheses are not paired correctly.

The world is bigger than only parentheses. Below, another (fixed size!) stack is used to match pairs of enclosing characters. Yes, 'push/pop' of a stack is a convenient way to make sure that 'nesting' meets expectations.

As for checking legitimacy of an expression, one would have to attempt to parse the expression according to some grammar rules. That is a somewhat more complicated.

#include <stdio.h>
#include <stdbool.h>

int main() {
    char *str = "{(foo)({gib(bar)gab;}) ((())) []Quick brown fox ";

    char stack[ 64 ] = { 0 };
    int stkInd = 1;
    bool good = true;
    for( char *cp = str; *cp; cp   ) {
        switch( *cp ) {
            case '(': stack[ stkInd   ] = ')'; break;
            case '{': stack[ stkInd   ] = '}'; break;
            case '[': stack[ stkInd   ] = ']'; break;
            case '<': stack[ stkInd   ] = '>'; break;

            case ')':
            case '}':
            case ']':
            case '>': good = *cp == stack[ --stkInd ]; break;
        }

        if(  stkInd >= sizeof stack ) {
            printf( "Stack Full!\n" );
            return -1;
        }

        if( !good ) {
            printf( "%s\n", str );
            printf( "%*s^---\n", cp - str, " " );
            printf( "Unmatched '%c'\n", *cp );
            return -1;
        }
    }

    while( stkInd > 1 ) {
        char c = stack[ --stkInd ];
        switch( c ) {
            case ')': c = '('; break;
            case '}': c = '{'; break;
            case ']': c = '['; break;
            case '>': c = '<'; break;
        }
        printf( "Unpairable %c\n", c );
    }

    return 0;
}

Looking again at your code, isempty( ) and display( ) may give you trouble as they both deal with a copy of the stack, rather than a pointer to the stack. Since your stack is dimensioned to match the full length of the original string, this may be viewed as wasteful. Passing the stack's address and using a pointer would be more efficient.