0001 void trim ( const char exp[], int& lo, int& hi ) { //删除exp[lo, hi]不含括号的最长前缀、后缀 0002 while ( ( lo <= hi ) && ( exp[lo] != '(' ) && ( exp[lo] != ')' ) ) lo++; //查找第一个和 0003 while ( ( lo <= hi ) && ( exp[hi] != '(' ) && ( exp[hi] != ')' ) ) hi--; //最后一个括号 0004 } 0005 0006 int divide ( const char exp[], int lo, int hi ) { //切分exp[lo, hi],使exp匹配仅当子表达式匹配 0007 int crc = 1; //crc为[lo, mi]范围内左、右括号数目之差 0008 while ( ( 0 < crc ) && ( ++lo < hi ) ) //逐个检查各字符,直到左、右括号数目相等,或者越界 0009 if ( exp[lo] == '(' ) crc ++; 0010 else if ( exp[lo] == ')' ) crc --; 0011 return lo; 0012 } 0013 0014 bool paren ( const char exp[], int lo, int hi ) { //检查表达式exp[lo, hi]是否括号匹配(递归版) 0015 trim ( exp, lo, hi ); if ( lo > hi ) return true; //清除不含括号的前缀、后缀 0016 if ( ( exp[lo] != '(' ) || ( exp[hi] != ')' ) ) return false; //首、末字符非左、右括号,则必不匹配 0017 int mi = divide ( exp, lo, hi ); //确定适当的切分点 0018 return paren ( exp, lo + 1, mi - 1 ) && paren ( exp, mi + 1, hi ); //分别检查左、右子表达式 0019 }