题解 | #有效括号序列#

C语言

bool isValid(char* s ) {

    // write code here

    char *st1, *st2;

    int st1_i = -1, st2_i = -1;

    int s_len = 0;

    char *tmp = s;

    while(*tmp != '\0'){        //获得s的长度

        tmp++;

        s_len++;

    }

    st1 = (char *)malloc(sizeof(char) * s_len); //动态申请栈空间

    st2 = (char *)malloc(sizeof(char) * s_len);

    tmp = s;

    while(*tmp != '\0'){        //将输入字符串s压入st1

        st1[++st1_i] = *tmp;

        tmp++;

    }

    while(st1_i != -1){         //如果st1栈不为空，继续循环

        if(st1[st1_i] == '}' || st1[st1_i] == ']' || st1[st1_i] == ')'){    //将st1栈顶的右括号压入st2

            st2[++st2_i] = st1[st1_i--];

        }else{

            if(st2_i == -1){     //如果st1的栈顶为左括号，且st2栈为空，则是非法序列

                free(st1), free(st2);

                return false;

            }

            if(st1[st1_i] == '{' && st2[st2_i] != '}'){  //如果st1 st2栈顶元素不匹配，则是非法序列

                free(st1), free(st2);

                return false;

            }else if(st1[st1_i] == '{' && st2[st2_i] == '}'){    //匹配则栈st1 st2弹栈，进入下一次循环

                st1_i--, st2_i--;

            }

            if(st1[st1_i] == '[' && st2[st2_i] != ']'){

                free(st1), free(st2);

                return false;

            }else if(st1[st1_i] == '[' && st2[st2_i] == ']'){

                st1_i--, st2_i--;

            }

            if(st1[st1_i] == '(' && st2[st2_i] != ')'){

                free(st1), free(st2);

                return false;

            }else if(st1[st1_i] == '(' && st2[st2_i] == ')'){

                st1_i--, st2_i--;

            }

        }

    }

    if(st1_i == -1 && st2_i == -1){  //当st1栈为空，退出循环，这是需要判断st2栈是否为空，都为空则表示括号序列合法

        free(st1), free(st2);

        return true;

    }else{

        free(st1), free(st2);

        return false;

    }

}