括号匹配

//裁剪字符串，掐头去尾只保留被括号包围的部分
void trim(const char exp[], int& lo, int& hi) {
    while ((lo <= hi) && (exp[lo] != '(') && (exp[lo] != ')'))
        lo++;
    while ((lo <= hi) && (exp[hi] != '(') && (exp[hi] != ')'))
        hi--;
}
//分割字符串，分割成左右，即"("与")"括号相同的多个部分
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;
}
//综合上述两部分，递归求解
bool paren(const 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 paren(exp, lo + 1, mi - 1) && paren(exp, mi + 1, hi);
}

//上述是递归版
//下面迭代版
bool paren(const char exp[], int lo, int hi) {
    stack<char> s;
    for (int i = 0; i <= hi; ++i) {
        switch (exp[i])
        {
        case '(':
        case '[':
        case '{':
            s.push(exp[i]);
            break;
        case ')':
            if ((s.empty()) || (s.top() != '('))
                return false;
            s.pop();
            break;
        case ']':
            if ((s.empty()) || (s.top() != '['))
                return false;
            s.pop();
            break;
        case '}':
            if ((s.empty()) || (s.top() != '{'))
                return false;
            s.pop();
            break;
        default:
            break;
        }
    }
    return s.empty();
}