Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
Description
You are given a string consisting of parentheses () and []. A string of this type is said to be correct:
- (a)
- if it is the empty string
- (b)
- if A and B are correct, AB is correct,
- (c)
- if A is correct, (A ) and [A ] is correct.
Write a program that takes a sequence of strings of this type and check their correctness. Your program can assume that the maximum string length is 128.
Input
The file contains a positive integer n and a sequence of n strings of parentheses () and [], one string a line.
Output
A sequence of Yes or No on the output file.
Sample Input
3
([])
(([()])))
([()[]()])()
Sample Output
Yes
No
Yes
对于一个初学者,对栈的使用会有疑惑,什么是栈?怎么用它?很多书上解释的并不清楚。
简单说一下:
栈 (stack)又称堆栈,是一种受限制的线性表,其限制是只允许在表的一端进行插入和删除。
允许操作的一端称为栈顶(top),不允许 操作的称为栈底(bottom),每每次删除的数据元素总是最后插入的数据元素,所以栈又称为“后入先出表”,这是和队列的区别。
栈的储存结构有2种:一种顺序储存结构(顺序栈),一种链式储存结构(链式栈)。
今天主要来看看如何实现一个栈的功能
首先,栈的基本功能有:
1. empty 判断堆栈是否为空
2. pop 向堆栈里面压入一个数据
3. push 向堆栈压入一个数据
4. size 返回当前堆栈长度(即内部数据个数)
5. top 得到堆栈栈顶数据
此题题意:
输入一个包含()和[]的括号序列,判断是否合法。
具体递归定义如下:1.空串合法;2.如果A和B都合法,则AB合法;3.如果A合法则(A)和[A]都合法。
注意输入可能有空串
直接用栈
#include<iostream>
#include<stack>
#include<cstring>
#include<cstdio>
using namespace std; bool judge(char a,char b)
{
if(a=='['&&b==']')return ;
if(a=='('&&b==')')return ;
return ;
} bool left(char a)
{
if(a=='['||a=='(')return ;
return ;
} int main()
{
int cas;
char s[];
cin>>cas;
getchar();
while(cas--)
{
stack<char>q;
gets(s);
if(strcmp(s,"\n")==)
{
cout<<"Yes"<<endl;
continue;
}
for(int i=;s[i];i++)
{
if(q.empty())
{
q.push(s[i]);
}
else if(!judge(q.top(),s[i]))
{
if(left(s[i]))
q.push(s[i]);
}
else q.pop();
}
if(q.empty()) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return ;
}
我自己的是下面这一种,可能更容易理解一些,也是栈的思想
#include<stdio.h>
#include<string.h>
int main()
{
int i,j,k,T;
int flag;
int s[],st,top;
char c[];
scanf("%d",&T);
getchar();
while(T--)
{
fgets(c,sizeof(c),stdin);
flag=;
j=;
for(i=; c[i]!='\n'; i++)
{
if(c[i]=='(')
s[j++]=;
else if(c[i]=='[')
s[j++]=;
else if(c[i]==')')
{
if(j!= && s[j-]==)
j--;
else
{
flag=;
break;
}
}
else if(c[i]==']')
{
if(j!= && s[j-]==)
j--;
else
{
flag=;
break;
}
}
else
{
flag=;
break;
}
}
if(flag==|| j!=)
printf("No\n");
else
printf("Yes\n");
}
return ;
}
看了别人代码加我百度才明白栈的用法,发现要学的好多。。