论坛 › 数据结构与算法 › 括号匹配，写的麻烦，运行超时，希望大佬们给看一下

百年c++ 发表于 2017-9-30 08:08:55

括号匹配，写的麻烦，运行超时，希望大佬们给看一下

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>


#define STACK_INIT_SIZE 20
#define STACKINCREMENT10
#define MAXBUFFER       10
typedef char ElemType;
typedef struct
{
   ElemType *base;
   ElemType *top;
   int stacksize;
}SqStack;


void InitStack(SqStack &S)
{
   S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
   if (!S.base)exit(OVERFLOW);
   S.top=S.base;
   S.stacksize=STACK_INIT_SIZE;
   return;
}

void Push(SqStack &S,ElemType e)
{
    if(S.top-S.base>=S.stacksize)
    {
      S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof (ElemType));
      if(!S.base)exit(OVERFLOW);
      S.top=S.base+S.stacksize;
      S.stacksize+=STACKINCREMENT;
    }
    *S.top++=e;
    return;
}

void Pop(SqStack &S,ElemType &e)
{
   if (S.top==S.base){return;};
   e=*--S.top;
}


int StackLen(SqStack S)
{
   return(S.top-S.base);
}


int main()
{
   SqStack S;
   char c,e;
   InitStack(S);
   scanf ("%c",c);//读入c
   while(c!='.')
   {
         switch(c)
         {
         case '(':
         case '[':
         case '{':
         Push(S,c);//如果是开始符，则入栈
         scanf("%c",c);//读入下一个符号
         if ('.'==c)
         {Pop(S,e);printf("NO\n",e);printf("%c-?",e);}//当开始符后面的符号直接是'.'的话，直接输出
         else break;//包含第一个字符是开始符的情况
         case '/':
         Push(S,c);
         scanf ("%c",c);
         Push(S,c);
         do
             {
               scanf ("%c",c);
             }while (c!='*'&&c!='.');
            if ('*'==c)
            {
                Push(S,c);
                scanf("%c",c);
                Push(S,c);
                scanf ("%c",c);
                break;
            }
             else {printf("NO\n");printf("/*-?");}
             break;
         case '*':
         printf ("NO\n");
         printf("?-*/");
         c='.';
         break;
         case ')':
         if (!StackLen(S)){printf("NO\n",c);printf ("?-%c");}
         else
         {
             Pop(S,e);
             if ('('!=e){printf("NO\n");printf("?-)");}
             else if('('==e)scanf("%c",c);
         }break;
          case ']':
         if (!StackLen(S)){printf("NO");printf("\n?-]");}
         else
         {
             Pop(S,e);
             if ('['!=e){printf("NO\n");printf("?-]");}
             else if('['==e)scanf ("%c",c);
         }break;
          case '}':
         if (!StackLen(S))printf("NO\n?-}");
         else
         {
             Pop(S,e);
             if ('{'!=e){printf("NO\n");printf("?-}");}
             else if('{'==e)scanf("%c",c);
         }break;
         }
   }
   if (!StackLen(S))printf ("\nYES");
   return 0;
}

weizhongyang 发表于 2017-10-20 13:18:32

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>


#define STACK_INIT_SIZE 20
#define STACKINCREMENT10
#define MAXBUFFER       10
typedef char ElemType;
typedef struct
{
   ElemType *base;
   ElemType *top;
   int stacksize;
}SqStack;


void InitStack(SqStack *S)
{
   S->base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
   if (!S->base)exit(OVERFLOW);
   S->top=S->base;
   S->stacksize=STACK_INIT_SIZE;
   return;
}

void Push(SqStack *S, ElemType e)
{
    if(S->top-S->base>=S->stacksize)
    {
      S->base=(ElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof (ElemType));
      if(!S->base)
                        exit(OVERFLOW);
      S->top=S->base+S->stacksize;
      S->stacksize+=STACKINCREMENT;
    }
    *S->top++=e;
    return;
}

void Pop(SqStack *S, ElemType *e)
{
    if (S->top==S->base)
        {
                return;
        };
    e=--S->top;
}


int StackLen(SqStack S)
{
   return(S.top-S.base);
}


int main()
{
   SqStack S;
   char c,e;
   InitStack(&S);
   scanf("%c",&c);//读入c
   while(c!='.')
   {
         switch(c)
         {
         case '(':
         case '[':
         case '{':
         Push(&S,c);//如果是开始符，则入栈
         scanf("%c",&c);//读入下一个符号
         if ('.'==c)
         {Pop(&S,&e);printf("NO\n");printf("%c-?",e);}//当开始符后面的符号直接是'.'的话，直接输出
         else break;//包含第一个字符是开始符的情况
         case '/':
         Push(&S,c);
         scanf("%c",&c);
         Push(&S,c);
         do
             {
               scanf("%c",&c);
             }while (c!='*'&&c!='.');
            if ('*'==c)
            {
                Push(&S,c);
                scanf("%c",&c);
                Push(&S,c);
                scanf("%c",&c);
                break;
            }
             else {printf("NO\n");printf("/*-?");}
             break;
         case '*':
         printf ("NO\n");
         printf("?-*/");
         c='.';
         break;
         case ')':
         if (!StackLen(S)){printf("NO\n");printf ("?-%c", c);}
         else
         {
             Pop(&S,&e);
             if ('('!=e){printf("NO\n");printf("?-)");}
             else if('('==e)scanf("%c",&c);
         }break;
          case ']':
         if (!StackLen(S)){printf("NO");printf("\n?-]");}
         else
         {
             Pop(&S,&e);
             if ('['!=e){printf("NO\n");printf("?-]");}
             else if('['==e)scanf("%c",&c);
         }break;
          case '}':
         if (!StackLen(S))printf("NO\n?-}");
         else
         {
             Pop(&S,&e);
             if ('{'!=e){printf("NO\n");printf("?-}");}
             else if('{'==e)scanf("%c",&c);
         }break;
         }
   }
   if (!StackLen(S))printf ("\nYES");
   return 0;
}

Code_mzh 发表于 2018-2-3 10:30:12

这两个都不能运行吧

查看完整版本: 括号匹配，写的麻烦，运行超时，希望大佬们给看一下