7-9 堆棧操作合法性

分數 20

全屏瀏覽題目

作者?DS課程組

單位?浙江大學

假設以S和X分別表示入棧和出棧操作。如果根據一個僅由S和X構成的序列，對一個空堆棧進行操作，相應操作均可行（如沒有出現刪除時棧空）且最后狀態也是棧空，則稱該序列是合法的堆棧操作序列。請編寫程序，輸入S和X序列，判斷該序列是否合法。

輸入格式:

輸入第一行給出兩個正整數N和M，其中N是待測序列的個數，M（≤50）是堆棧的最大容量。隨后N行，每行中給出一個僅由S和X構成的序列。序列保證不為空，且長度不超過100。

輸出格式:

對每個序列，在一行中輸出YES如果該序列是合法的堆棧操作序列，或NO如果不是。

輸入樣例：

4 10
SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX

輸出樣例：

YES
NO
NO
NO

代碼長度限制

16 KB

時間限制

400 ms

內存限制

64 MB

#include <iostream>
#include <string.h>
using namespace std;
int main(){int a,b,c=0;string q;cin>>a>>b;for(int i=0;i<a;i++){cin>>q;c=0;for(int j=0;j<q.size();j++){if(q[j]=='S'){c++;if(c>b)break;}else{c--;if(c<0)break;}}if(c==0)printf("YES\n");elseprintf("NO\n");}return 0;
}