括号匹配(二)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;  
    }  
}          
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,776评论 0 33
  • Android 自定义View的各种姿势1 Activity的显示之ViewRootImpl详解 Activity...
    passiontim阅读 173,532评论 25 708
  • “龙生九子不成龙,各有所好”是说每个人都有自己的喜好、特长和自己的思想,而年轻人的思想和老一辈的观念碰撞在一起,除...
    胡小雪丶阅读 188评论 0 0
  • 去年的九月,我做出一个决定:把“将来”想做的事提早到“现在”-于是我开始了学习绘画。 一年多来,看到...
    蜻蜓点点水阅读 759评论 20 18
  • 面对困难,也许你会看到乌云后的一片彩虹;逃避困难,也许你会遇到另外一个你更加无法逃避的困难!乐观面对吧,你的生活更...
    妹那么简单Eunice阅读 231评论 0 0