题解 | #有效括号序列#
有效括号序列
https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2
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;
}
}
