括号匹配

Description

  给定一串由左小括号"("和右小括号")"组成的串，判断其是否匹配。如(a+b+(c+d))的括号是匹配的，((a+c+)+f)+g*(g+))的括号是匹配的。

分析

  每个")"总是和它最近的"("匹配。

AC代码

思路1

  假设读到一个"("，我们就把key自增，读到")"，就自减，如果括号是匹配的话，最后key的值应该是0（当然这是在这中间，key不小于0的情况下）。如果key小于0就说明，没有"("，就已经有")"。

#include <iostream>
#include <cstring>
using namespace std;
int main()
{
	char s[101];
    int key = 0;
    cin >> s;
    for(char *begin = s,*end = s + strlen(s);begin != end;++begin)
    {
        if(*begin == '(')
            ++key;
        else if(*begin = ')')
            --key;
        if(key < 0)
            break;
    }
    if(key)
        cout << "NO" << endl;
    else
        cout << "YES" << endl;
	return 0;
}

思路2

  上面的key就好比栈的元素个数，所以我们可以利用栈来解决这个问题，下面利用数组作为栈。

#include <iostream>
#include <cstring>
using namespace std;
int main()
{
    char s[101];
    int top = 0;
    cin >> s;
    int len = strlen(s);
    char *stack = new char[len];
    for(char *end = s + len,begin = s;begin!=end;++begin)
    {
        if(*begin == '(')
            stack[top++] = '(';
        else if(*begin = ')')
            --top;
        if(top < 0)
            break;
    }
    delete[] stack;
    if(top)
        cout << "NO";
    else
        cout << "YES";
    return 0;
}

  使用栈的好处，就是知道左括号与右括号匹配，当弹栈时，弹出的'('和刚读到的')'就是一对。