检查括号匹配,形如如下的字符串:
[([][])] 认为是匹配的。
而[(][])这种认为是不匹配的。
算法很简单,就是栈:
(1)如果是左括号([{等,直接入栈(使得原有在栈中的所有未消解的期待括号的紧迫级别下降一位)。
(2)如果是右括号,比如],则栈顶要么是与它匹配的左括号如[,否则就是括号不匹配。
(3)如果所有字符串都处理完,栈是空的,则是匹配的,否则不匹配。
代码如下:
// 1 for succ, 0 for false
int kuohao(char* str, struct Stack* stack)
{
int n = strlen(str);
int i = 0;
// Each char
for(i=0;i<n;i++)
{
char c = str[i];
char top;
// If left kuohao, push
if(c=='(' || c=='[' || c=='{')
{
stack_push(stack, c);
continue;
}
// Switch for righ kuohao or err char
stack_top(stack, &top);
switch(c)
{
case ')':
if(top=='(')
{
stack_pop(stack, &top);
} else
{
return 0;
}
break;
case ']' :
if(top=='[')
{
stack_pop(stack, &top);
} else
{
return 0;
}
break;
case '}' :
if(top=='{')
{
stack_pop(stack, &top);
} else
{
return 0;
}
break;
default:
return 0;
break;
}
}
// Empty for succ
if(stack_isempty(stack))
{
return 1;
} else
{
return 0;
}
}