题目

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

有效字符串需满足：

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

来源：https://leetcode-cn.com/problems/valid-parentheses/

解题思路

做一个空栈，读入字符直到字符尾。如果字符是一个开放符号，这将其推入栈中。如果字符是一个封闭符号，则当栈空时报错。否则将栈元素弹出。如果弹出的符号不是对应的开放符号，则报错。在字符遍历结束后，如果栈非空则报错。

注意括号交叉的情况如 （[）

代码

栈的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/* stack */
struct Node;
typedef struct Node* PtrToNode;
typedef PtrToNode Stack;
struct Node {
    char element;
    PtrToNode next;
};
/* API */
Stack  createStack() {
    Stack s;
    s = (Stack)malloc(sizeof(struct Node));
    if (s == NULL) {
        // cout << "ERROR:out of space" << endl;
    }
    s->next = NULL;
    return s;
};
void push(Stack s, char str) {
    PtrToNode tmpNode = (PtrToNode)malloc(sizeof(struct Node));
    if (tmpNode == NULL) {
        // cout << "ERROR:out of space" << endl;
    }
    tmpNode->next = s->next;
    tmpNode->element = str;
    s->next = tmpNode;
};
bool isEmpty(Stack s) {
    return s->next == NULL;
};
PtrToNode pop(Stack s) {
    if (isEmpty(s)) {
        // cout << "ERROR:stack empty" << endl;
    }
    PtrToNode tmpNode = s->next;
    s->next = tmpNode->next;
    return tmpNode;
};

验证匹配逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
bool isValid(char * testCode){
Stack s = createStack();
    bool result = true;
    int index = 0;
    while (index < strlen(testCode)) {
        char curChar = testCode[index];
        if (curChar != ']' && curChar != ')' && curChar != '}') {
            push(s, curChar);
        } else {
            if (isEmpty(s)) {
                // cout << "括号无可匹配项" << endl;
                result = false;
                break;
            }
            // 找到匹配的括号
            char targetChar;
            if (curChar == ']') {
                targetChar = '[';
            } else if (curChar == ')') {
                targetChar = '(';
            } else {
                targetChar = '{';
            }
            PtrToNode topNode = pop(s);
            while (topNode->element != targetChar) {
                if (!isEmpty(s)) {
                    //栈顶元素是开放括号 但不是匹配括号
                    if (topNode->element != targetChar && (topNode->element == '[' || topNode->element == '(' || topNode->element == '{')) {
                        //Error
                        result = false;
                        // cout << "括号发生交叉" << endl;
                        break;
                    }                                       topNode = pop(s);
                } else {
                    result = false;
                    // cout << "括号无可匹配项" << endl;
                    break;
                }
            }
            if (result == false) {
                break;
            }
        }
        index++;
    }
    if(!isEmpty(s)){ result = false;}
return result;
}