检查括号匹配,形如如下的字符串:
[([][])] 认为是匹配的。
而[(][])这种认为是不匹配的。
算法很简单,就是栈:
(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; } }