直接用栈模拟即可，数组可做，但因为这节数据结构是栈，为了期末考试还是手写一下栈的操作，值得注意的是，这道题用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 ;
}