0001 /****************************************************************************************** 0002 * Data Structures in C++ 0003 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3 0004 * Junhui DENG, deng@tsinghua.edu.cn 0005 * Computer Science & Technology, Tsinghua University 0006 * Copyright (c) 2003-2019. All rights reserved. 0007 ******************************************************************************************/ 0008 0009 bool paren ( const char exp[], int lo, int hi ) { //表达式括号匹配检查,可兼顾三种括号 0010 Stack<char> S; //使用栈记录已发现但尚未匹配的左括号 0011 for ( int i = lo; i <= hi; i++ ) /* 逐一检查当前字符 */ 0012 switch ( exp[i] ) { //左括号直接进栈;右括号若与栈顶失配,则表达式必不匹配 0013 case '(': case '[': case '{': S.push ( exp[i] ); break; 0014 case ')': if ( ( S.empty() ) || ( '(' != S.pop() ) ) return false; break; 0015 case ']': if ( ( S.empty() ) || ( '[' != S.pop() ) ) return false; break; 0016 case '}': if ( ( S.empty() ) || ( '{' != S.pop() ) ) return false; break; 0017 default: break; //非括号字符一律忽略 0018 } 0019 return S.empty(); //整个表达式扫描过后,栈中若仍残留(左)括号,则不匹配;否则(栈空)匹配 0020 }