7-2 堆栈操作合法性 (20分)

发表于 更新于 分类于 Disqus： 本文字数： 2.3k 阅读时长 ≈ 4 分钟

假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入S和X序列，判断该序列是否合法。

输入格式:

输入第一行给出两个正整数N和M，其中N是待测序列的个数，M（≤50）是堆栈的最大容量。随后N行，每行中给出一个仅由S和X构成的序列。序列保证不为空，且长度不超过100。

输出格式:

对每个序列，在一行中输出YES如果该序列是合法的堆栈操作序列，或NO如果不是。

输入样例：

1
2
3
4
5
4 10
SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX

输出样例：

1
2
3
4
YES
NO
NO
NO
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<iostream>
#include<string>
using namespace std;

#define MAXSIZE  100
#define ADDSIZE  10
typedef int Status;
typedef char SElemType;

typedef struct {
    SElemType *base;
    SElemType *top;
    int stacksize;
} SqStack;

Status Initstack(SqStack &s,int e=MAXSIZE)
{
    s.base=new SElemType[e];
    s.top=s.base;
    s.stacksize=e;
    return 1;
}


Status push(SElemType e,SqStack &s)
{
    if(s.top-s.base>=s.stacksize)
    {
        /*s.base=(SElemType*)realloc(s.base,(s.stacksize+ADDSIZE)* sizeof(SElemType));
        if(!s.base)
            exit(EOVERFLOW);
        s.top=s.base+s.stacksize;
        s.stacksize+=ADDSIZE;*/
        return 0;
    }
    *s.top++=e;
    return 1;
}

Status pop(SElemType &e,SqStack &s)
{
    if(s.top==s.base)return 0;
    e=*--s.top;
    return 1;
}

Status GetTop(SElemType &e,SqStack &s)
{
    if(s.top==s.base)return 0;
    e=*(s.top-1);
    return 1;
}

bool Isright(string s,int e)
{
    int i=0,f=1;
    SqStack sq;
    Initstack(sq,e);
    while (s[i] != '\0')
    {
        if(s[i]=='S') {
            if (push(s[i],sq) == 1)
                i++;
            else
                {
                f = 0;
                break;
            }
        }
        else {
            if (pop(s[i],sq) == 1)
                i++;
            else {
                f = 0;
                break;
            }
        }
    }
    if(sq.top==sq.base&&s[i]=='\0')
        f=1;
    else
        f=0;
    return f == 1;
}
bool IsRight(string s,int L)
{
    int i=0,flag=1;
    SqStack sq;
    Initstack(sq,L);
    while(s[i]!='\0')
    {
        if(s[i]=='S')
        {
            if(push(s[i],sq)==1)
                i++;
            else
            {
                flag=0;
                break;
            }
        }
        else
        {
            if(pop(s[i],sq)==1)
                i++;
            else
            {
                flag=0;
                break;
            }
        }
    }
    if((sq.top==sq.base) && s[i]=='\0')
        flag=1;
    else
        flag=0;
    return flag == 1;
}

int main()
{
    int m,n;
    string ss;
    cin>>m>>n;
    for (int u = 0; u < m; ++u) {
        cin>>ss;
        if (IsRight(ss,n)== true)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
}