CODEWITHSUNDEEP
c
pmac89
pmac89

Reputation: 418

Bracket error matching

I'm trying to get brackets to match. What needs to be matched is the '()', '[]', '{}' and '[{}]' is supposed to output true. I don't want it to work for the cases such as '[{]}' or '[{}'. Though, right now my code is not outputting yes for the correct match even when it should be true.

Code (updated):

int booleanBalanceBracket(aStack *theStack){
    aStack *balanceStack = NULL;

    while(theStack){
        if(theStack->token == '[' || theStack->token == '{' || theStack->token == '(')
            balanceStack = pushBracket(theStack->token, balanceStack);
        else if(theStack->token == ']' || theStack->token == '}' || theStack->token == ')'){
            if(balanceStack == NULL)
                return 0;
            else
                balanceStack = popBracket(balanceStack);
        }
        theStack = theStack->nextItem;
    }
    if(balanceStack == NULL){
        return 1;
    }else{
        return 0;
    }

}
int isMatching(int token1, int token2){
    if(token2 == '(' && token1 == ')')
        return 1;
    else if(token2 == '{' && token1 == '}')
        return 1;
    else if(token2 == '[' && token1 == ']')
        return 1;
    else
        return 0;
}

Upvotes: 0

Views: 185

Answers (2)

BLUEPIXY
BLUEPIXY

Reputation: 40145

your code problem is this line

balanceStack = popBracket(balanceStack);

Does not receive a value obtained by pop. It is also necessary to compare the value popped.

The Example of a simple string

bool booleanBaranceBracket(const char *s){
    static const char *left  = "{([";
    static const char *right = "})]";
    size_t len = strlen(s);
    char *p, stack[len];
    int sp = -1;
    int i;
    for(i=0;i<len;++i){
        if(p = strchr(left, s[i]))
            stack[++sp] = s[i];
        else if(p = strchr(right, s[i])){
            char ch;
            if(sp == -1) return false;
            ch = stack[sp--];
            if(ch != left[p - right]) return false;
        }
    }
    return sp == -1;
}

Upvotes: 0

Jim Balter
Jim Balter

Reputation: 16406

Try this simple algorithm:

for each char c in the input
   if opener
       push on stack
   else if closer
       if stack is empty or doesn't match
           return false
       else
           remove top of stack

return true if stack is empty, else false

This can be slightly optimized to avoid the empty stack checks and also to avoid an explicit check for EOF by pushing EOF onto the stack initially, and matching EOF to EOF.

Upvotes: 2

Related Questions