题解 | #有效括号序列#
有效括号序列
https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2
C语言，使用数组来做栈，会出现占用空间过大，等下出个优化版本
#define ST_SIZE 5
static char st1[ST_SIZE] = {0}; //栈st1用来装输入的字符串
static char st2[ST_SIZE] = {0}; //栈st2用来装st1弹出的右括号
static int st1_i = -1, st2_i = -1;
bool isValid(char* s ) {
// write code here
char *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栈为空，则是非法序列
return false;
if(st1[st1_i] == '{' && st2[st2_i] != '}') //如果st1 st2栈顶元素不匹配，则是非法序列
return false;
else if(st1[st1_i] == '{' && st2[st2_i] == '}'){ //匹配则栈st1 st2弹栈，进入下一次循环
st1_i--, st2_i--;
}
if(st1[st1_i] == '[' && st2[st2_i] != ']')
return false;
else if(st1[st1_i] == '[' && st2[st2_i] == ']'){
st1_i--, st2_i--;
}
if(st1[st1_i] == '(' && st2[st2_i] != ')')
return false;
else if(st1[st1_i] == '(' && st2[st2_i] == ')'){
st1_i--, st2_i--;
}
}
}
if(st1_i == -1 && st2_i == -1) //当st1栈为空，退出循环，这是需要判断st2栈是否为空，都为空则表示括号序列合法
return true;
else
return false;
}
