1. 题目描述

problem link

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

2. 解题

栈最典型的应用之一，括号匹配。

如果遇到了正括号：

• 直接无脑压栈，栈容量++

如果遇到了反括号：

• 如果当前栈容量 == 0，则当前反括号不可能匹配，返回false
• 否则让栈顶元素与当前反括号进行匹配，匹配上了栈容量--，没匹配上返回false

最终如果栈里还有元素则出现了不匹配，返回false，否则返回true

3. 代码

typedef int bool;
#define true 1
#define false 0

bool isValid(char * s) {
    char stack[5000] = { 0 };
    int size = 0;
    char* ptr = s;

    while (*ptr) {
        if (*ptr == '(' || *ptr == '{' || *ptr == '[') {  // 左括号
            stack[size++] = *ptr++;
        }
        else {
            if (size == 0) {  // 只有反括号没有正括号
                return false;
            }
            if ((stack[size - 1] == '(' && *ptr == ')') ||
                (stack[size - 1] == '[' && *ptr == ']') ||
                (stack[size - 1] == '{' && *ptr == '}')) {  // 匹配上了
                size--;
                ptr++;
            }
            else {  // 没匹配上
                return false;
            }
        }
    }

    return size == 0 ? true : false;
}