Parentheses Matching

Given a string containing only (, ), [, ], {, and }, determine whether it is valid. In a valid string, every opening bracket must be closed by the same type of closing bracket in the correct order.

A stack can determine bracket validity. When traversal encounters an opening bracket, a matching closing bracket is expected later. Because the most recent opening bracket must close first, push it onto the stack. When a closing bracket appears, pop the opening bracket at the top and check whether the types match. If they do not match, or no opening bracket is available, the string is invalid. After traversal, an empty stack means that every opening bracket was closed.

A valid string must have even length. An odd-length string can therefore be rejected before traversal begins.

bool is_valid_bracket(char *bracket) {
    stack_t *stack = stack_create();
    for (int i = 0; bracket[i] != '\0'; i++) {
        char c = bracket[i];
        if (c == '(' || c == '[' || c == '{') {
            stack_push(stack, c);
        } else {
            if (stack_is_empty(stack)) {
                return false;
            }
            char top = stack_pop(stack);
            if (!((c == ')' && top == '(') || (c == ']' && top == '[') ||
                  (c == '}' && top == '{'))) {
                return false;
            }
        }
    }
    bool valid = stack_is_empty(stack);
    stack_destroy(stack);
    return valid;
}