20括号匹配

题目

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

示例 1：

输入：s = “()”
输出：true
示例 2：

输入：s = “()[]{}”
输出：true
示例 3：

输入：s = “(]”
输出：false
示例 4：

输入：s = “([)]”
输出：false
示例 5：

输入：s = “{[]}”
输出：true

思路

降维打击

• 缩小问题规模
• 将大问题 (三种括号) 化为小问题 (一种括号)
• 再从小问题退出大问题解法

一种括号序列

代码演示一

bool isValid(char *s) {
    int lnum = 0;
    int length = strlen(s);
    for (int i = 0; i < length; i++) {
        switch (s[i]) {
            case '(' : {
                lnum++;
            } break;
            case ')' : {
                lnum--;
            } break;
            default : return false;
        }
        if (lnum > 0) continue;
        return false;
    }
    return !lnum;
}
// 思路：一种括号时，左括号数量必须大于右括号数量
// 且没有遍历完括号序列s时，左括号数量大于右括号数量，
// 也就是lnum > 0。
// 遍历完括号序列后lnum必须为0。

思考

1. 我们可以获得怎样的思考方式
2. +1等价为进，-1等价为出。
3. 一对括号（）等价为一个完整的事件
4. (())可以看出事件与事件之间的完全包含关系
5. 由括号的等价变换，得到一个新的数据结构

思考

• 系统栈也是栈，能不能用系统栈解决问题？
• 系统爆栈是怎么回事？
• 能用栈解决的问题，都能递归解决

栈和树

可以处理具有完全包含关系的问题

• 回到大问题

代码演示

• 自己写的栈

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Stack {
    char *val;
    int p, maxSize;
} Stack;

void init_Stack(Stack *s, int len) {
    s->val = (char *)malloc(sizeof(char)* len);
    s->p = 0;
}
bool empty_Stack(Stack *s) {
    return !(s->p);
}

void push_Stack(Stack *s, char ch) {
    s->val[s->p++] = ch;
}

void pop_Stack(Stack *s) {
    --(s->p);
}
char seek_Stack(Stack *s) { //寻找
    return s->val[s->p - 1];
}

bool isValid(char *s) {
    Stack stack;
    int length = strlen(s);
    init_Stack(&stack, length);
    for (int i = 0; i < length; i++) {
        switch (s[i]) {
            case '(' :
            case '{' :
            case '[' : {
                push_Stack(&stack, s[i]);
            } break;
            case ')' : {
                if (empty_Stack(&stack)) return false;
                if (seek_Stack(&stack) != '(') return false;
                pop_Stack(&stack);
            } break;
            case '}' : {
                if (empty_Stack(&stack)) return false;
                if (seek_Stack(&stack) != '{') return false;
                pop_Stack(&stack);
            } break;
            case ']' : {
                if (empty_Stack(&stack)) return false;
                if (seek_Stack(&stack) != '[') return false;
                pop_Stack(&stack);
            } break;
        }
    }
    return empty_Stack(&stack);
}
int main() {
    char s[100];
    scanf("%s", s);
    int a = isValid(s);
    printf("%d\n", a);
    return 0;
}

• 系统栈

代码演示

#include <stdio.h>
#include <string.h>
bool judgeOne(char *s, int *i, int d) {
    bool flag = true;
    int j = d;
//    printf("in %d\n", *i);
    while (s[*i] && flag) {
        switch (s[*i]) {
            case '(' : {
                ++(*i);
                flag = judgeOne(s, i, d + 1);
                if (s[*i] == ')') {
                    ++(*i), flag &= true;
                } else if (s[*i] == ']' || s[*i] == '}' || s[*i] == '\0'){
                    flag = false;
                }
            } break;
            case '[' : {
                ++(*i);
                flag = judgeOne(s, i, d + 1);
                if (s[*i] == ']') {
                ++(*i), flag &= true;
                } else if (s[*i] == ')' || s[*i] == '}' || s[*i] == '\0'){
                    flag = false;
                }
            } break;
            case '{' : {
                ++(*i);
                flag = judgeOne(s, i, d + 1);
                if (s[*i] == '}') {
                ++(*i), flag &= true;
                } else if (s[*i] == ')' || s[*i] == ']' || s[*i] == '\0'){
                    flag = false;
                }
            } break;    
            case ']' :
            case '}' :
            case ')' :
                return j == 0 ? false : true && flag;
            default :
                return false;        
        }
    }
    return flag;
}

bool isValid(char *s) {
    int i = 0, len = strlen(s);
    bool flag = true;
    while (i < len && flag) {
        flag &= judgeOne(s, &i, 0);
    }
    return flag; 
}

int main() {
    char ch[100];
    scanf("%s", ch);
    bool a = isValid(ch);
    printf("%d\n", a);
    return 0;
}

自己写的

代码演示

bool isValid(char *s) {
    int len = strlen(s);
    if (len & 1) return false;
    char stack[(len >> 1) + 1];
    int i = 0;
    for (int j = 0; j < len; j++) {
        switch(s[j]) {
            case '(' :
            case '[' :
            case '{' : {
                stack[i++] = s[j];
            } break;
            case ')' : {
                if (!i) return false; //i为0，没有括号跟它匹配了，提前结束
                if (stack[i - 1] != '(') return false;
                --i;
            } break;
            case ']' : {
                if (!i) return false;
                if (stack[i - 1] != '[') return false;
                --i;
            } break;
            case '}' : {
                if (!i) return false;
                if (stack[i - 1] != '{') return false;
                --i;
            } break;

            default : return false;

        }
    }
    return !i;
}