AcWing 3678. 模拟出入栈游戏
原题链接
简单
作者:
NFYD
,
2022-09-07 11:22:18
,
所有人可见
,
阅读 343
- 和42. 栈的压入、弹出序列 本质上一样,就是把数据类型从
int
换成了char
- 思路:借助一个栈,扫描入栈序列,每次先把当前扫描到的数压入栈中,然后判断:当当前栈顶与出栈序列的第k(k从0开始)个元素相同时,就弹出栈顶,k++, 然后继续往后做,扫描完整个入栈序列时,如果栈为空,那么说明出栈序列合法,否则不合法
#include <iostream>
#include <stack>
using namespace std;
string s; // 出栈序列
string pushed = "abcdefghijklmnopqrstuvwxyz"; // 入栈序列
stack<char> stk;
int main()
{
while (cin >> s)
{
stk = stack<char>();
int k = 0;
for (auto x: pushed)
{
stk.push(x);
while (stk.size() && stk.top() == s[k] && k < s.size())
{
stk.pop();
k ++ ;
}
}
if (stk.empty()) puts("yes");
else puts("no");
}
return 0;
}