Leetcode20有效的括号

20有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/valid-parentheses 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

栈
执行用时：0 ms
内存消耗：5.3 MB

bool isValid(char *s)
{
    int MAX_STACK_SIZE = strlen(s) / 2 + 1;
    char *stack = malloc(MAX_STACK_SIZE * sizeof(char));
    int i = 0;
    while (*s != '\0')
    {
        if (*s == '(' || *s == '[' || *s == '{')
        {
            if (i < MAX_STACK_SIZE)
                stack[i++] = *s;
            else
                printf("stack overflow\n");
        }
        else if (i == 0)
            return false;
        else if (*s == ')')
        {
            if (stack[--i] != '(')
                return false;
        }
        else if (*s == ']')
        {
            if (stack[--i] != '[')
                return false;
        }
        else if (*s == '}')
        {
            if (stack[--i] != '{')
                return false;
        }
        else
            return false;
        s++;
    }
    free(stack);
    if (i == 0)
        return true;
    else
        return false;
}