|
今天只完成了一道题，学习了出栈序列的合法性，也因为这个卡了一个晚上。
写的题是第二周任务（栈+队列+搜索模板）中的c题：
您将获得一个由括号（ ）和[ ]组成的字符串。这种类型的字符串被认为是正确的：
- 如果是空字符串
- 如果A和B是正确的，AB是正确的，
- 如果A是正确的，（A） 和 [A] 是正确的。
编写一个程序，该程序采用此类型的字符串序列并检查其正确性。您的程序可以假定最大字符串长度为128。
思路：
将左括号输入，将右括号用于消除。按照栈的定义，左括号可以与右括号对应。
#include<iostream>
#include<string.h>
#include<stack>
using namespace std;
const int max_n = 1e5 + 10;
char Q[max_n];
int top = 0;
void push (char x){//入栈
Q[top ++] = x;
}
char pop(){//出栈
return Q[--top];
}
void pop1(){//退顶
--top;
}
int main()
{
int n ;
scanf("%d" , &n);
char s[130];
int a[1001];
char o;
for( int m = 0 ; m < 1001 ; m ++){
a[m] = 0;
}
int m ;
stack<char>v;
for( m = 0 ; m <= n ; m ++){
gets(s);
int u = strlen(s);
if(u == 0){a[m] = 1; continue;}//根据题意若无输入直接Yes
int t ;
for( t = 0 ; t < u ; t ++){
if( s[t] == '(' || s[t] == '[' ){//如果输入是左括号将括号存入
push( s[t] );
}
else if(top == 0){break;}
else if(top!=0){
if(s[t] == ')') o = '(';//若输入为右括号，将右括号变为左括号，用于消去栈中的括号
if(s[t] == ']') o = '[';
if(pop() == o){continue;}
else break;
}
}
if( t == u && top == 0)a[m] = 1;
else a[m] = 0;
while(top!=0){//将栈顶退回
pop1();
}
}
for( m = 1 ; m <= n ; m ++){
if(a[m] == 1)printf("Yes\n");
else printf("No\n");
}
return 0;
}
出栈的合法性：
因为栈的限制“后进先出”，所以栈的输出有限制，但是可以通过入栈出栈的顺序改变输出结果。不过还是有限制。
例题
现在有n个元素分别是1,2,3,...,n，我们想知道通过一个栈，在n次push/pop后，出栈序列可能是什么样的。例如n是5，那么入栈次序就是1,2,3,4,5，如果我们希望出栈次序同样是1,2,3,4,5，那只要每push一个数，就立即pop一个数。如果我们希望出栈次序是3,2,4,5,1，那么我们先让1,2,3入栈，然后pop出来3和2，接着4入栈后马上pop，再就是5入栈后马上pop，最后再把栈里的1pop出。再例如，如果我们希望出栈次序是5,4,1,2,3，这是办不到的，如果要让5最先出栈，那么出栈次序只可能是5,4,3,2,1
思路：
用另一个栈来存数，将待测序列依次与i(1~N)比对，若相同继续对比，若不同则将i存入新栈，直至序列有数与相等。然后继续将序列与i对比若不同则与新栈出栈的数对比，若相同则继续，如不同则合法。
题解还在写，因为没有看清题意，正在加班赶。后续补上。
了解了一下c++里面的stack，用这个可以不用自己写入栈，出栈了。很方便，但是需要了解栈的底层代码，初学时还是需要自己写，多了解一些。
|