当前位置: 代码迷 >> 综合 >> goj 1446 判断栈的输出是否合法
  详细解决方案

goj 1446 判断栈的输出是否合法

热度:44   发布时间:2023-12-16 03:49:26.0

这道题开始按照思路是:从输入序列的第一个字符和目标序列的第一个字符比较,如果输入序列的字符和输出目标序列对应不相等,则让其一直入栈,碰到相等的情况就目标序列的下标后移一位,输入序列的下标也后移一位,然后再让后移一位的输出目标序列字符与栈顶比较,如果与它相等的不在栈顶则一定在后面,如果后面也没有则输出no。

AC代码:

#include<cstdio>
#include<stack>
#include<string>
#include<iostream>
using namespace std;
int n,indx;
int main(){while(scanf("%d",&n)!=EOF){string s1,s2;stack<int> s;cin>>s1>>s2;indx=0;for(int i=0;i<n;i++){s.push(s1[i]);while(!s.empty()&&s.top()==s2[indx]){s.pop();indx++;}}if(indx==n)printf("yes\n");elseprintf("no\n");}return 0;
}
虽然思路是对了,但编程的时候没有想到这么做,直接先将输入字符入栈,然后再让输出目标序列的字符对应比较栈顶。