一道简单的数据结构题 qduoj

点击打开链接

栈中所保留元素均为 ‘（’

如从左至右遍历数组 遇‘（’则入栈 遇‘）’则分情况讨论

1.栈空 则说明其左边再无‘（’可与其配对 由题意得 该‘）’无论和谁配对都需要转为‘（’ 因此通过num++来保留此次操作

2.栈非空 则说明其左边尚有‘（’可与其配对，则两者抵消 该‘）’不需入栈且栈顶的‘（’弹出

遍历结束 栈中所有元素均为原字符串中需要改变的‘（’ （包括1情况中由‘）’转变而来）

由题意得 此时栈中元素数必为偶数 除二 再加上num值 即为所求

#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;

char a[1000001];

int main()
{
    int n,i,t,sum,ans;
    while(scanf("%s",a)!=EOF)
    {
        stack <char> s;
        n=strlen(a),sum=0;
        for(i=0;i<n;i++)
        {
            if(a[i]=='(')
            {
                s.push(a[i]);
            }
            else
            {
                if(!s.empty())
                {
                    s.pop();
                }
                else
                {
                    s.push(a[i]);
                    sum++;
                }
            }
        }
        ans=sum+s.size()/2;
        printf("%d\n",ans);
    }
    return 0;
}