栈的应用——括号匹配

对表达式的括号匹配检查是语法检查的必要环节，解决该类问题，同理可以推广用于各类语言的符号匹配（例如markdown使用两个美元符号$进行公式界定）。

递归

先考虑简单情况：只有圆括号，使用“+”号表示表达式的连接。
一般地，任意表达式可以按如下规则分解：

$$S=S_{0}+“(”+S_{1}+“)”+S_{2}+S_{3}$$

其中和不含括号，且中左右括号数相等，则匹配当且仅当与均匹配。
根据分治策略，可以不断将表达式如此划分，递归地判断、是否匹配。

代码示例

void trim( const char exp[], int& lo, int& hi )  //删除exp[lo,hi]不含括号的最长前后缀
{
    while ( (lo<=hi) && (exp[lo]!='(') && (exp[lo]!=')') ) lo++;
    while ( (lo<=hi) && (exp[hi]!='(') && (exp[hi]!=')') ) lo++;
}

int divide (const char exp[], int lo, int hi)
{
    int mi = lo;
    int crc=1;  //左右括号数之差
    while( (0<crc) && (++mi<hi) )  //逐个检查，直到左右括号数相等或者越界
    {
        if( exp[mi]==')' ) crc--;
        if( exp[mi]==')' ) crc--;
    }
    return mi;  //若mi<=hi,则为合法切分点；否则局部不匹配 why?
}

bool paren (const char exp[], int lo, int hi)
{
    trim (exp, lo, hi);
    if(hi<lo) return true;
    if ( exp[lo]!='(' ) return false;
    if ( exp[hi]!=')' ) return false;
    int mi = divide(exp, lo, hi);
    if(mi>hi) return false;  //why?
    return paren(exp, lo+1, mi-1) && paren(exp, mi+1, hi);
}//O(n^2)

对于代码的一些细节问题，需要单独考虑退化情况。
例如，在截除操作后，lo可能会大于hi，这样会在函数paren里返回true;
lo可能等于hi，此时划分以后mi=hi+1，在paren里返回false；
切分时mi可能等于hi,再下一层递归中lo+1>mi-1,mi+1>hi均返回true。
由此可见，直接用递归实现括号匹配算法，既复杂又需要慎重考虑边界情况，一不小心便会出错，同时该算法时间复杂度达到了n的平方，效率低下。再者，对于多种括号的匹配，该算法更是无能为力。因此有必要进一步优化。

迭代

实际上，只要将push、pop操作分别与左右括号对应，则长度为n的栈混洗，必然与由n对括号组成的合法表达式彼此对应。据此，借助栈结构，只需一趟遍历，即可在线性时间判断出括号是否匹配。

bool paren( const char exp[], int lo, int hi )
{
    stack<char> S;
    for ( int i=lo;i<=hi;i++ )
        swich(exp[i])
        {
            case '(':case '[':case '{':S.push(exp[i]); break;
            case ')':if(S.empty()||(S.pop()!='(')) return false; break;
            case ']':if(S.empty()||(S.pop()!='[')) return false; break;
            case '}':if(S.empty()||(S.pop()!='{')) return false; break;
            default: break;  //忽略非括号字符
        }
    return S.empty();  //扫描后栈中仍留有左括号则不匹配，栈空则匹配
}//O（n)

以上代码，将具体的待匹配字符修改，即可满足其他二元匹配的需要。