括号匹配（二）nyoj

#include<stdio.h>  
#include<string.h>  
  
char _stack[205];  
int head = -1;  
int rear;  
void pop()  
{  
    head--;  
}  
  
void push(char ch)  
{  
    _stack[++head] = ch;  
}  
  
char top()  
{  
    return _stack[head];  
}  
  
int main()  
{  
    int n;  
    int i;  
    int j;  
    int cnt;  
    int run;  
    char str[105];  
    scanf("%d",&n);  
    while(n--)  
    {  
        cnt = 0;  
        head = -1;  
        scanf("%s",str);  
        for(i=0; i<strlen(str); i++)  
        {  
            switch(str[i])  
            {  
            case '(':  
            case '[':  
                push(str[i]);  
                break;  
            case ']':  
                if(top()=='[')  
                    pop();  
                else if(top()=='(')  
                {  
                    run = 1;  
                    for(j=0; j<head; j++)  
                    {  
                        if(_stack[j]=='[')  
                        {  
                            pop();  
                            cnt++;  
                            i--;  
                            run = 0;  
                            break;  
                        }  
                    }  
                    if(run)  
                        cnt++;  
                }  
                else  
                    cnt++;  
                break;  
            case ')':  
                if(top()=='(')  
                    pop();  
                else if(top()=='[')  
                {  
                    run = 1;  
                    for(j=0; j<head; j++)  
                    {  
                        if(_stack[j]=='(')  
                        {  
                            pop();  
                            cnt++;  
                            i--;  
                            run = 0;  
                            break;  
                        }  
                    }  
                    if(run)  
                        cnt++;  
                }  
                else  
                    cnt++;  
                break;  
            default:  
                break;  
            }  
        }  
        cnt+=head+1;  
        printf("%d\n",cnt);  
    }  
}  

RT记录一下 标程式DP也帖一下以后看

#include<iostream>  
#include<cstdio>  
#include<cstring>  
  
  
using namespace std;  
const int maxn=110;  
char tab[maxn];  
int f[maxn][maxn];  
  
  
int fun(int i,int j)  
{  
    if(i>j)return 0;  
    if(f[i][j]>=0)return f[i][j];  
    if(i==j)return f[i][j]=1;  
    int va=maxn;  
    if((tab[i]=='('&&tab[j]==')') || (tab[i]=='['&&tab[j]==']'))  
        va=fun(i+1,j-1);  
    for(int mid=i;mid<j;mid++){  
        va=min(va,fun(i,mid)+fun(mid+1,j));  
    }  
    return f[i][j]=va;  
}  
  
  
int main()  
{  
       
    int n;  
    scanf("%d",&n);  
    for(int i=0;i<n;i++){  
        memset(f,-1,sizeof(f));  
        memset(tab,0,sizeof(tab));  
        scanf("%s",tab);  
        cout<<fun(0,strlen(tab)-1)<<endl;  
    }  
}