【数据结构】栈的应用——括号匹配问题
括号匹配问题:
给一个字符串,其中包含小括号、中括号、大括号,求该字符串中的括号是否匹配。
例如:
()()[]{} 匹配
([{()}]) 匹配
[]( 不匹配
[(]) 不匹配
利用堆栈的思路:
建立一个堆栈,然后遍历字符串,如果是‘(‘,‘{‘.‘[‘,则入栈,否则判断当前字符串和栈顶元素是否是一对括号;要注意的是,需要提前判断栈是否为空,为空的时候取top是违法的的,所以只要为空就入栈,然后执行下一次循环,而且,只要循环过程中出现一次栈顶元素和当前元素不匹配的情况,就可以跳出循环返回false了。
int isBracket(char left,char right) { if(left == ‘(‘ && right == ‘)‘) return 1; if(left == ‘[‘ && right == ‘]‘) return 1; if(left == ‘{‘ && right == ‘}‘) return 1; return 0; } int isValidParentheses( char *str ) { int len; int i; T_Stack stack; int buf[100]; int tmp; StackInit( &stack, buf, sizeof(buf)/sizeof(buf[0])); len = strlen( str ); for( i = 0; i < len; i++ ) { if( StackIsEmpty( &stack ) ) { StackPush( &stack, str[i] ); continue; } StackTop( &stack, &tmp ); if( str[i] == ‘(‘ || str[i] == ‘[‘ || str[i] == ‘{‘) { StackPush( &stack, str[i]); } else if( isBracket( tmp, str[i] ) ) { StackPop( &stack, &tmp ); } else { return 0; } } return ( StackIsEmpty( &stack ) ); } int main( void ) { char *str[] = { "()()[][]{}", "[(])", "[]( ", "([{()}])", "(([{()}]) " }; int i; for( i = 0; i < sizeof(str)/sizeof(str[0]); i++ ) { printf("%s\r\n", isValidParentheses(str[i]) ? "match" : "not match"); } system("pause"); return 0; }
参考引用:
https://www.jianshu.com/p/be1dc368200d
https://www.cnblogs.com/hedeyong/p/7841548.html
相关推荐
koushr 2020-11-12
zhangxiafll 2020-11-13
kikaylee 2020-10-31
范范 2020-10-28
MILemon 2020-10-22
hugebawu 2020-10-12
LauraRan 2020-09-28
shenwenjie 2020-09-24
omyrobin 2020-09-23
guangcheng 2020-09-22
qiangde 2020-09-13
hanyujianke 2020-08-18
晨曦之星 2020-08-14
xiesheng 2020-08-06
KAIrving 2020-08-02
xiesheng 2020-08-02
范范 2020-07-30
chenfei0 2020-07-30