每日一题(三) 7.29

每日一题(三) 7.29

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

有效字符串需满足：

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

题解思路

使用数组做栈，两个指针i和j，分别代表字符串和栈顶+1，先判断是否是({[,如果是进栈，不是则判断栈是否为空，空则返回false；如果栈顶是相对应字符，j–；否则，返回false。
最后再判断栈中是否还有元素，没有元素则false，否则true。

代码

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool isValid1(char * s){
    int i=0,j=0;
    char stack[100000];

    while(s[i]!='\0'){
        if((s[i]==')' || s[i]==']' || s[i]=='}') && j==0){
            return false;
        }
        if(s[i]=='(' || s[i]=='{' || s[i]=='['){
            stack[j++] = s[i++];
        }
        else{
            if(s[i]==')' && stack[j-1] != '('){
                return false;
            }
            else if(s[i]=='}'&& stack[j-1] != '{'){
                return false;
            }
            else if(s[i]==']' && stack[j-1] != '['){
                return false;
            }
            i++;
            j--;
        }
    }
    if(j==0){
        printf("chenggong");
        return true;

    }else{
        return false;
    }
}

bool isValid(char * s){
    int i = 0;
    char str[10000] = {0} ;
    int len = strlen(s);
    if(len % 2 != 0){
        printf("字符串长度为奇数：%s","失败\n");
        return false;
    } else if (len == 0 ){
        printf("字符串长度为0:%s","成功\n");
        return true;
    }

    for(int l = 0; l < strlen(s); l++){

        printf("%s\n","进入循环");
        printf("第%d次循环\n",l+1);
        if(s[l] == '(') {
            printf("l为:%d\n", l);
            printf("i为:%d\n", i);
            str[i] = s[l];
            printf("s[l]为:%c\ts为:%s\n", s[l],s);
            printf("str字符串为:%s\n", str);
            i++;
//            continue;
        } else if (s[l] == '['){
            printf("l为:%d\n", l);
            printf("i为:%d\n", i);
            str[i] = s[l];
            printf("str字符串为:%s\n", str);
            i++;
        } else if (s[l] == '{'){
            str[i] = s[l];
            i++;
        } else if (s[l] == ')'){
            if(strlen(str) == 0){
                printf("%s","失败\n");
                return false;
            } else{
                for (int j = i-1; j >= 0; --j) {
                    printf("i为:%d\n", i);
                    printf("j为:%d\n", j);
                    printf("str字符串为:%s\n", str);
                    if (str[j] == '('){

                        str[j] = '\0';
                        printf("修改后的字符串为:%s\n", str);
                        i--;
                        break;
                    }else if (str[j] != '('){
                        printf("%s","失败");
                        return false;

                    }
                    else{
                        printf("%s","失败");
                        return false;
                    }
                }
            }
        } else if (s[l] == ']'){
            if(strlen(str) == 0){
                printf("%s","失败");
                return false;
            } else{
                for (int j = i-1; j >= 0; --j) {
                    printf("i为:%d\n", i);
                    printf("j为:%d\n", j);
                    printf("str字符串为:%s\n", str);
                    if (str[j] == '['  ){
                        str[j] = '\0';
                        printf("修改后的字符串为:%s\n", str);
                        i--;
                        break;
                    } else if (str[j] != '['){
                        printf("%s","失败");
                        return false;

                    }

                    else{
                        printf("%s","失败");
                        return false;
                    }

                }


            }

        } else if (s[l] == '}'){
            printf("%s\n","进入");
            if(strlen(str) == 0){
                printf("%s","失败\n");
                return false;
            } else{
                for (int j = i-1; j >= 0; --j) {
                    printf("i为:%d\n", i);
                    printf("j为:%d\n", j);
                    printf("str字符串为:%s\n", str);
                    if (str[j] == '{'){
                        str[j] = '\0';
                        i--;
                        break;


                    }else if (str[j] == '{'){
                        printf("%s","失败");
                        return false;

                    }
                    else{
                        printf("%s","失败");
                        return false;
                    }
                }

            }
        }
    }
    if(strlen(str) == 0){
        printf("%s","成功\n");
        return true;
    }else{
        printf("zheli%s","失败\n");
        return false;
    }

}

int main() {
//    isValid("{[]}");
    isValid1("{[]}");
    return 0;
}