PTA 7-2 符号配对

直接用栈模拟即可，数组可做，但因为这节数据结构是栈，为了期末考试还是手写一下栈的操作，值得注意的是，这道题用gets函数在PTA上会编译错误，用scanf("%[^\n]", str)会有一个样例无法通过，最后我使用了string读入数据，应该是我对scanf格式化读入不够了解，有知道的朋友可以评论区告诉我，非常感谢

附上代码：

 #include <stdio.h>

 #include <malloc.h>

 #include <stdlib.h>

 #include <string.h>

 #include <iostream>

 #include <string>

 using namespace std;

 //函数状态码定义

 #define TRUE        1

 #define FALSE       0

 #define OK          1

 #define ERROR       0

 #define INFEASIBLE -1

 #define OVERFLOW   -2

 typedef int Status;

 typedef char SElemType;

 #define STACK_INIT_SIZE 500

 #define STACKINCREMENT 10

 typedef struct {

     SElemType *base;

     SElemType *top;

     int stacksize;

 }SqStack;

 Status InitStack(SqStack &S) {

     S.base = (SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType));

     if(!S.base) exit(OVERFLOW);

     S.top = S.base;

     S.stacksize = STACK_INIT_SIZE;

     return OK;

 }//InitStack

 Status GetTop(SqStack &S, SElemType &e) {

     if(S.top == S.base)

         return ERROR;

     e = *(S.top - );

     return OK;

 }//GetTop

 Status Push(SqStack &S, SElemType e) {

     if(S.top - S.base >= S.stacksize) {

         S.base = (SElemType * )realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));

         if(!S.base)

             exit(OVERFLOW);

         S.top = S.base + S.stacksize;

         S.stacksize += STACKINCREMENT;

     }

     *S.top++ = e;

     return OK;

 }//Push

 Status Pop(SqStack &S, SElemType &e) {

     if(S.top == S.base)

         return ERROR;

     e = *--S.top;

     return OK;

 }//Pop

 char change(char ch){

     if(ch == '(')

         return ')';

     if(ch == '{')

         return '}';

     if(ch == '[')

         return ']';

     if(ch == 'a')

         return 'b';

     if(ch == ')')

         return '(';

     if(ch == '}')

         return '{';

     if(ch == ']')

         return '[';

     if(ch == 'b')

         return 'a';

 };

 int main()

 {

     SqStack sta;

     InitStack(sta);

     char ch, ptr[] = {}, cnt = ;

     char ans = ' '; // ( -> 1, { -> 2, [ -> 3, /* -> 4

     string str;

     while(getline(cin, str)) {

         if(str == ".")

             break;

         for(int i = ; i < str.size(); ++i) {

             if(str[i] == '(' || str[i] == '{' || str[i] == '[' || str[i] == ')' || str[i] == '}' || str[i] == ']')

                 ptr[cnt++] = str[i];

             else if(str[i] == '/' && str[i + ] == '*')

                 ptr[cnt++] = 'a', ++i;

             else if(str[i] == '*' && str[i + ] == '/')

                 ptr[cnt++] = 'b', ++i;

         }

     }

     for(int i = ; i < cnt; ++i) {

         if(ptr[i] == '(' || ptr[i] == '{' || ptr[i] == '[' || ptr[i] == 'a')

             Push(sta, ptr[i]);

         else {

             if(GetTop(sta, ch) == OK) {

                 if(ptr[i] == change(ch)) {

                     Pop(sta, ch);

                 }

                 else {

                     ans = ch;

                     break;

                 }

             }

             else {

                 ans = ptr[i];

                 break;

             }

         }

     }

     if(ans == ' ' && GetTop(sta, ch) == OK) {

         ans = ch;

     }

     if(ans == ' ')

         printf("YES");

     else {

         printf("NO\n");

         if(ans == '(' || ans == '{' || ans == '[')

             printf("%c-?",ans);

         else if(ans == 'a')

             printf("/*-?");

         else if(ans == ')' || ans == '}' || ans == ']')

             printf("?-%c",ans);

         else

             printf("?-*/");

     }

     return ;

 }

巴特西

PTA 7-2 符号配对

最新文章

热门文章