亲，您未登录哦！ 登录 | 注册
首页  |  社区  |  工具箱  |  代码库  |  博客  |  招聘  |  文章  |  新闻  |  下载  |  读书
回 帖 发 新 帖 刷新版面

主题：第49次编程比赛题目

neverPE [专家分：1620] 发布于 2007-02-23 20:11:00

题目：给出一个包含各种括号的表达式，判断括号是否配对。括号配对的条件：括号必须先左后右，并且左右括号数量相等；对于多重括号，从外到内嵌套顺序为：{} -> [] -> () -> <>。例如{[(<>)]}。

接口： bool match(char* str);   合法返回true， 否则返回false。

输入范例： 
{[(<>)]}
{}
<(>)
<()>

返回：
true
true
false
false

    大过年的， 也不能让大家累着：）这次的题目相对来说很简单，容易理解，容易上手，容易做对。 但牛人们还是有发挥的余地， 速度最快并不容易。 

    结束时间：下周一中午12点，结束前本帖隐藏回复。 有任何问题另外开帖询问，或者参考以前的规则。
最后更新于：2007-02-23 20:16:00
本帖地址：  http://bbs.pfan.cn/post/218845.html

回复列表 （共33个回复）

21 楼

rickone [专家分：15390] 发布于 2007-02-24 22:16:00

给论坛里的朋友先拜个年，祝大家在新的一年里工作顺利，学习进步！

不知道这题neverPE有什么妙招，我直接用map，不违规吧

#include <iostream>
#include <stack>
#include <map>
using namespace std;
map<char,int> g_ciMap;
void initmap()
{
    g_ciMap['{']=1;
    g_ciMap['[']=2;
    g_ciMap['(']=3;
    g_ciMap['<']=4;
    g_ciMap['}']=9;
    g_ciMap[']']=10;
    g_ciMap[')']=11;
    g_ciMap['>']=12;
}
bool match(char* str)
{
    stack<int> iStack;
    int t=0,len=strlen(str),l=0;
    for(int i=0;str[i];++i)
    {
        if(l+i>len)
            return false;
        map<char,int>::iterator it=g_ciMap.find(str[i]);
        if(it==g_ciMap.end())
            continue;
        int v=(*it).second;
        if(v<5)
        {
            if(v<t)
                return false;
            iStack.push(v);
            l++;
            t=v;
        }
        else
        {
            if(v!=t+8)
                return false;
            iStack.pop();
            l--;
            if(iStack.empty())
                t=0;
            else
                t=iStack.top();
        }
    }
    return iStack.empty();
}

int main()
{
    initmap();
    char str[256];
    while(cin>>str)
    {
        if(match(str))
            cout<<"match"<<endl;
        else
            cout<<"not match"<<endl;
    }
    return 0;
}

没有和直接用if比较的比较，当是偷懒了~

22 楼

merry05 [专家分：8920] 发布于 2007-02-25 14:16:00

/*本人用C，正确返回1，错误返回0*/
int match(char *str)
{
    int stack[5]={5,0,0,0,0},i=0;
    while(*str!='\0')
    {
        if(*str=='{')
        {
            if(stack[i]<=4) return 0;
            stack[++i]=4;
            str++;
        }
        else if(*str=='[')
        {
            if(stack[i]<=3) return 0;
            stack[++i]=3;
            str++;
        }
        else if(*str=='(')
        {
            if(stack[i]<=2) return 0;
            stack[++i]=2;
            str++;
        }
        else if(*str=='<')
        {
            if(stack[i]<=1) return 0;
            stack[++i]=1;
            str++;
        }
        else if(*str=='}')
        {
            if(stack[i--]!=4) return 0;
            str++;
        }
        else if(*str==']')
        {
            if(stack[i--]!=3) return 0;
            str++;
        }
        else if(*str==')')
        {
            if(stack[i--]!=2) return 0;
            str++;
        }
        else if(*str=='>')
        {
            if(stack[i--]!=1) return 0;
            str++;
        }
    }
    if(i!=0) return 0;
    return 1;
}

23 楼

hazf2008 [专家分：290] 发布于 2007-02-25 17:38:00

#include <string.h>
#include <stdio.h>

bool match(char* str)    //{[(<>)]}
{
    if (str == NULL)
        return false;
    int len = strlen(str);
    if (len == 0)
        return false;
    char *strTmp = str;
    int *iTmp = new int[len];
    int sum = 0;

    for (int i=0; i<len; i++)
    {
        switch (*strTmp++)
        {
        case '{':
            iTmp[i] = -4;
            break;
        case '[':
            iTmp[i] = -3;
            break;
        case '(':
            iTmp[i] = -2;
            break;
        case '<':
            iTmp[i] = -1;
            break;
        case '>':
            iTmp[i] = 1;
            break;        
        case ')':
            iTmp[i] = 2;
            break;        
        case ']':
            iTmp[i] = 3;
            break;
        case '}':
            iTmp[i] = 4;
            break;        
        default:
            return false;
        }
        sum += iTmp[i];
    }
    
    if (sum)
        return false;

    int halfLen = len/2-1;
    for (i=0; i<halfLen; i++)
    {
        if (iTmp[i]>=iTmp[i+1] || iTmp[i]>0)
            return false;        
    }

    for (i=len-1; i>halfLen; i--)
    {
        if (iTmp[i]<=iTmp[i-1] || iTmp[i]<0)
            return false;        
    }    
    return true;
}

void main()
{
    char str[6][10] = {"{[(<>)]}", "{}", "<(>)", "<()>", "[[]]", ""};
    for (int i=0; i<6; i++)
    {
        if (match(str[i]))
            printf("true;\n");
        else 
            printf("false;\n");
    }
}

24 楼

独行者 [专家分：1280] 发布于 2007-02-25 17:55:00

#include <stdio.h>
#include <string.h>
bool match(char* str);
int main(void)
{
    bool c;
    char str[20];
    gets(str);
    c=match(str);
    if(c==true)
        printf("true\n");
    else
        printf("false\n");
    return 0;
}
bool match(char* str)
{

    int i,j,len,top=-1,a[20];;
    len=strlen(str);
    for(i=0;i<len;i++)
    {
        switch(str[i])
        {
        case '{' : top++; a[top]=3; for(j=0;j<top;j++) if(a[j]<=a[top]||a[j]-a[j+1]>1) return false;
                                    break;
        case '[' : top++; a[top]=2; for(j=0;j<top;j++) if(a[j]<=a[top]||a[j]-a[j+1]>1) return false;
                                    break;
        case '(' : top++; a[top]=1; for(j=0;j<top;j++) if(a[j]<=a[top]||a[j]-a[j+1]>1) return false;
                                    break;
        case '<' : top++; a[top]=0; for(j=0;j<top;j++) if(a[j]<=a[top]||a[j]-a[j+1]>1) return false;
                                    break;
        case '}' : if(top==-1||a[top]!=3) return false;
                   else top--;
                   break;
        case ']' : if(top==-1||a[top]!=2) return false;
                   else top--;
                   break;
        case ')' : if(top==-1||a[top]!=1) return false;
                   else top--;
                   break;
        case '>' : if(top==-1||a[top]!=0) return false;
                   else top--;
                   break;
        }
    }
    if(top!=-1) return false;
    else return true;
}

25 楼

szh [专家分：380] 发布于 2007-02-25 18:20:00

#include <stack>
using namespace std;
int compare(char *str, int i)
{
    switch(str[i])
    {
    case '{':    return 1;
    case '}':    return 5;
    case '[':    return 2;
    case ']':    return 6;
    case '(':    return 3;
    case ')':    return 7;
    case '<':    return 4;
    case '>':    return 8;
    }
    return 0;
}
bool match(char *str)
{
    int i;
    stack<int>    s;
    s.push(0);

    for(i=0; str[i]!='\0'; i++)
    {
        int j=compare(str, i);
        if(j)
        {
            if(j>4)
            {
                if((j-4)==s.top())
                    s.pop();
                else
                    return false;
            }
            else
            {
                if(j>=s.top())
                    s.push(j);
                else
                    return false;
            }
        }
    }
    return true;
}

26 楼

笑十三狼 [专家分：1040] 发布于 2007-02-25 23:44:00

用的C语言
#include<stdio.h>
int match(char* str)
{
    char cMoban[9]={'{','[','(','<','>',')',']','}','\0'};
    int nMoban[9]={4,3,2,1,-1,-2,-3,-4,0};
    char *p1=cMoban,*p=str;
    int *p2=nMoban;
    int sum=0,gengzong=4;
    while(*p)
    {
        char *p1=cMoban;
        int *p2=nMoban;
        while(*p!=*p1)
        {
            p1++;
            p2++;
        }
        sum+=*p2;
        if((gengzong-*p2)<0)
          return 0;
        gengzong=*p2;
        p++;
    }
    if(sum==0)
       return 1;
    else
       return 0;
}
int main()
{
    char s[81];
    scanf("%s",s);
    if(match(s)==1)
       printf("true");
    else
       printf("false");
    getch();    /* 请不要删除此行 */
    return 0;
}

27 楼

songfei [专家分：40] 发布于 2007-02-26 01:43:00

没有学过数据结构 
这个堆栈写的有点丢人
呵呵

#define LEN_STR 10000  //字符串长度 题目没有给出限制

#include <iostream>

using namespace std;

char k[LEN_STR];
int point=-1; 
 
void Put(char ch)
{ 
point++;
k[point]=ch;
}

char Out()
{
  point--;
  return k[point+1];
}

bool match(char *str)
{
   int len;
   int i; 
   char flag=1; 
   int max=0; 
   char temp; 
   len=strlen(str);
   
   if(len%2!=0)return false; //配对 一定是偶数 
   
   for(i=0;i<len;i++)
   {
      temp=str[i]; 
      if(temp=='{'||temp=='['||temp=='('||temp=='<') Put(str[i]);
      else if(temp=='}'){if(Out()!='{'){flag=0;break;}else {max=6;}}
      else if(temp==']'){if(Out()!='['||(max>5)){flag=0;break;}else max=5;}
      else if(temp==')'){if(Out()!='('||(max>4)){flag=0;break;}else max=4;}
      else if(temp=='>'){if(Out()!='<'||(max>3)){flag=0;break;}else max=3;}
    }
    if(point==(len-1))return false;  //都是左括号 
    if(flag==0)return false;
    else return true;
}


int main(int argc, char *argv[])
{
    char c[LEN_STR]; 
    cin>>c; 
    cout<<match(c)<<endl;
    return EXIT_SUCCESS;
}

Dev C++ 4.9 编译通过

28 楼

freeeerf [专家分：5440] 发布于 2007-02-26 07:52:00

#include<iostream>
using namespace std;

//1.本来要用C写的,但C里面没有bool类型,只好用C++的头文件了,但代码还是C的写法
//2.用a,b,c,d四个值表示括号的出现次数,初始值是0,右括号++,左括号--,最后为0则表示配对.
//3.程序将字符串遍历一次,时间复杂度是O(n).
bool match(char *str)
{
    int i,len,a=0,b=0,c=0,d=0;
    
    for(i=0,len=strlen(str);i<len;++i)
    {
        switch(str[i])
        {
        case '{':
            if(b!=0||c!=0||d!=0)
                return false;
            ++a;
            break;
        case '}':
            if(b!=0||c!=0||d!=0)
                return false;
            --a;
            break;
        case '[':
            if(c!=0||d!=0)
                return false;
            ++b;
            break;
        case ']':
            if(c!=0||d!=0)
                return false;
            --b;
            break;
        case '(':
            if(d!=0)
                return false;
            ++c;
            break;
        case ')':
            if(d!=0)
                return false;
            --c;
            break;
        case '<':
            ++d;
            break;
        case '>':
            --d;
            break;
        default:
            break;
        }
    }
    if(a!=0)
        return false;
    else 
        return true;   
}

int main()
{
    char s[]="<()>";
    

    if(match(s))
        puts("Yes");
    else 
        puts("No");
    
    system("pause");
    return 0;
}

29 楼

ldb2741 [专家分：2570] 发布于 2007-02-26 10:24:00

#include "iostream"
#include "string.h"
using namespace std;

bool match(char *str)
{

    char s[]="{[(<";
    char k[]="}])>";
    int a[]={1,2,3,4};
    int len=strlen(str);
    int i,j=len-1,count,m,n,a1,a2;
    for(i=0;i<len/2;i++)
    {
        for(count=0;count<4;count++)
            if(s[count]==str[i])
                a1=count;
        for(count=0;count<4;count++)
            if(k[count]==str[j])
                a2=count;
            if(a1!=a2)
                return 0;
            j--;
    }
    i=0;
    while(i<len/2-1)
    {
        for(count=0;count<4;count++)
        {
            if(s[count]==str[i])
            { 
                m=count;
                break;
            }
        }
        i++;
        for(count=0;count<4;count++)
        {
            if(s[count]==str[i])
            {
                n=count;
                break;
            }
        }
        if(a[m]>=a[n]) return 0;
    } 
    return 1;
    
}

int main()
{
    char a[10],b[10],c[10],d[10];
    cout<<"input four strings:"<<endl;
    cin>>a;
    cin>>b;
    cin>>c;
    cin>>d;
    if(match(a)) cout<<"true"<<endl;
    else cout<<"false"<<endl;
    if(match(b)) cout<<"true"<<endl;
    else cout<<"false"<<endl;
    if(match(c)) cout<<"true"<<endl;
    else cout<<"false"<<endl;
    if(match(d)) cout<<"true"<<endl;
    else cout<<"false"<<endl;
}






30 楼

雪光风剑 [专家分：27190] 发布于 2007-02-26 10:35:00

#include<iostream>
#include<conio.h>
using namespace std;

int len(char*);
bool match(char*);

int main(void)
{
    char* input;
    cout<<"please input the formula to match:";
    cin>>input;
    if(match(input))
      cout<<"ture";
    else
      cout<<"false";  
    system("pause");
    return 0;  
}

int len(char* ori)
{
    int count=0;
    for(;*ori++!='\0';count++);
    return count;
}
    
bool match(char* ori)
{
     int lpos=0,rpos;
     rpos=len(ori);
     while(lpos!=len(ori))
     {
       if(ori[lpos]=='{')
       {
               for(;ori[rpos]!='}';rpos--);
               if(rpos==0)
                    return false;
       }
       if(ori[lpos]=='[')
       {
               for(;ori[rpos]!=']';rpos--);
               if(rpos==0)
                    return false;
       }
       if(ori[lpos]=='(')
       {
               for(;ori[rpos]!=')';rpos--);
               if(rpos==0)
                    return false;
       }
       if(ori[lpos]=='<')
       {
               for(;ori[rpos]!='>';rpos--);
               if(rpos==0)
                    return false;
       }
     }    
     return true;
}
//跳错，说内存不能为written，但是感觉算法上应该没有问题啊

我来回复

您尚未登录，请登录后再回复。点此登录或注册

程序员工具箱 new

  • 通用文本转换
  • 域名whois查询
  • XML格式化压缩
  • Meta标签生成工具
  • 文本转图片
  • useragent工具
  • JavaScript库CDN服务
  • UNIX时间戳转换
  • PHP手册
  • 在线抽奖
  • 更多工具

    • 代码片段

  • 模拟键盘（不可按）
  • 碰撞的唐三
  • 精彩奥运热点赛事的实时采集
  • 获取天气动态信息
  • 文件查找
  • python大数据抓取京东电脑销量数据
  • 爬虫技术不仅仅支持数据采集
  • 抓取脉脉APP上的职业信息
  • 爬虫中多线程的运用
  • 四则运算以及一元二次方程
  • 欢迎来共享你的NB代码

    • 本版新帖

  • 以前写的一个String类
  • 产生哈夫曼编码的源代码
  • 两极大数运算，源程序示例
  • 冰玉的原代码在这里，主要参考《电脑爱好者》及《c游戏编程从入门到精通》，没有时间，你可以参考！哈哈。
  • 那位高手指教如何用Turbo c调用.pcx图象文件
  • 24点中的不可能组合
  • 求任意多个整数的公倍数
  • 算24点全集之程序
  • TURBO C 2.0的汉化文件！
  • 10点半游戏
  • 高手心得（转载）！
  • 有没人会二叉树的生成啊?????十万火急
  • 广义表类
  • 树类
  • 一些有关递归回溯的程序