数据结构：栈的应用举例——括号匹配的检验

2. 括号匹配的检验

如果表达式中包含括号，当程序中含有这类表达式时，在代码编译过程中，必然会检查括号是否匹配，这是一项必需的语法检查环节。

（1）迭代版

此处假设表达式中只含有左、右圆括号，借助栈检验左右圆括号是否匹配。

• 每当读入一个左括号，则直接入栈，等待相匹配的右括号；
• 每当读入一个右括号，若栈顶为左括号，将当前栈顶的左括号出栈。否则返回 false （表示不匹配）；
• 直到表达式扫描完毕，且栈为空时返回 true，否则返回 false 。

【算法描述】

//括号匹配检验：迭代版
bool math(char exp[], int n){int i = 0;char e;bool match = true;LinkStack * st;  //本例使用链栈，使用顺序栈亦可InitStack(st);   //初始化栈while(i < n && match){//扫描 exp 中的所有字符if(exp[i] == "("){//当前字符为左括号，将其入栈Push(st, exp[i]);} else if (exp[i] == ")"){//当前字符为右括号if(GetTop(st, e) == true){//成功取到栈顶元素 eif (e != '(')    //栈顶元素不为 '('match = false; //表示不匹配else             //栈顶元素为 '('Pop(st, e)；  //将栈顶元素出栈} else {match = false;  //无法取栈顶元素时表示不匹配}}i++;  //继续处理其他字符}if(!StackEmpty(st))  //栈不空时表示不匹配match = false;DestroyStack(st);  //销毁栈return match;
}

【算法分析】

• 时间复杂度：$O(n)$ ，$n$ 是字符串的长度
• 算法运行过程中的辅助空间是栈 st ，其大小不会超过 $n$ ，故空间复杂度为 $O(n)$ 。

此算法的流程控制简单，而且便于推广至多类括号并存的场合。它自左向右逐个考查各字符， 忽略所有非括号字符。凡遇到左括号，无论属于哪类均统一压入栈中。若遇右括号，则弹出栈顶的左括号并与之比对。若二者属于同类，则继续检查下一字符；否则，即可断定表达式不匹配。 当然，栈提前变空或者表达式扫描结束后栈非空，也意味着不匹配。

（2）递归版

仅仅考虑圆括号，一般地，可以将表达式 S 分解为下面的形式：
$$S=S_0{+}^{"}{(}^{"}+S_1{+}^{"}{)}^{"}+S_2+S_3$$
其中 $S_0$ 和 $S_3$ 不含括号。

很显然，当且仅当 $S_1$ 和 $S_2$ 的括号匹配（上式中为了表示明显地表示括号，将 ${}^{"}{(}^{"}$ 和 $S_1$ 、${}^{"}{)}^{"}$ 和 $S_2$ 分开，事实上左右括号应该分别包含在 $S_1$ 和 $S_2$ 之内），表达式 $S$ 的括号必匹配。

因此，可以使用分治算法，将表达式 $S$ 划分为子表达式 $S_0、S_1、S_2、S_3$ ，分别递归地判断 $S_1$ 和 $S_2$ 是否匹配。

【算法描述】

void trim(char exp[], int &lo, int &hi){//删除 exp[lo, hi]不含括号的最长前缀、后缀while((lo <= hi) && (exp[lo] != '(') && (exp[lo] != ')'))lo++; //查找第一个括号while((lo <= hi) && (exp[hi] != '(') && (exp[hi] != ')'))hi--; //查找最后一个括号
}int divide(char exp[], int lo, int hi){//切分 exp[lo, hi]，使 exp 匹配仅当子表达式匹配int mi = lo;int crc = 1; //crc 为 [lo, mi] 范围内左右括号的数目之差while((0 < crc) && (++mi < hi)){//逐个检查字符，直到左右括号数目相等或者越界if(exp[mi] == ')')crc--; //遇到右括号减一if(exp[mi] == '(')crc++; //遇到左括号加一}return mi; //若 mi<=hi，则为合法切分点；否则，意味着局部不匹配
}bool math(char exp[], int lo, int hi){trim(exp, lo, hi); //清除不含括号的前缀、后缀if (lo > hi)return true;if(exp[lo] != '(')return false; //首字符非左括号，则必不匹配if(exp[hi] != ')')return false; //末字符非右括号，则必不匹配int mi = divide(exp, lo, hi); //确定适当的切分点if(mi > hi)return false; //切分点不合法，意味着局部以至整体不匹配return math(exp, lo+1, mi-1) && math(exp, mi+1, hi); //分别检查左、右子表达式
}

• trim() 函数用于截除表达式中不含括号的头部和尾部，即前缀 $S_0$ 和后缀 $S_3$ 。
• divide() 函数对表达式做线性扫描，并动态地记录已经扫描的左、右括号数目之差。如此，当已扫过同样多的左、右括号时，即确定了一个合适的切分点 mi，并得到子表达式 S_1 = exp(lo, mi) 和 S_2 = exp(mi, hi] 。
• 递归地检查 $S_1$ 和 $S_2$ ，即可判断原表达式是否匹配。

【算法分析】

在最坏情况下，divide() 需要线性时间，且递归深度为 $O(n)$ ，故以上算法共需 $O(n^2)$ 时间。

注意：上述方法难以处理含有多种括号的表达式，故不如迭代版适用性广。