堆栈操作合法性

梦里梦外; 2022-07-29 11:42 124阅读 0赞

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

输入格式:

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

输出格式:

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

输入样例：

4 10  
SSSXXSXXSX  
SSSXXSXXS  
SSSSSSSSSSXSSXXXXXXXXXXX  
SSSXXSXXX  
输出样例：

YES  
NO  
NO  
NO

在问答里面看到这样一道题。感觉和前几天做的华为笔试题有些类似。所以贴过来。题目不难（我感觉）,代码如下：

#include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    
    int main()
    {
        int N,M;
        vector<string> str_vec;
        while(cin>>N>>M)
        {
            for(int i=0;i<N;i++)
            {
                string str;
                int cur=0;
                int i=0;
                cin>>str;
                for(i=0;i<str.size();i++)
                {
                       if(str[i]=='S'&&cur<M)
                       {
                           cur++;
                       }
                       else if(str[i]=='X'&&cur>0)
                       {
                           cur--;
                       }
                       else
                       {
                          str_vec.push_back("NO");
                          break;
                       }
                }
                if(i==str.size()&&cur==0)
                {
                    str_vec.push_back("YES");
                }
                else if(i==str.size())
                {
                    str_vec.push_back("NO");
                }
            }
        }
    
        for(int i=0;i<str_vec.size();i++)
        {
            cout<<str_vec[i]<<endl;
        }
    
        return 0;
    }

给的测试用例过了，但是其他的没有测试，如有错误，请批评指正！