转载

UVa 673 Parentheses Balance（栈的使用）

栈

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 1;   if(a=='('&&b==')')return 1;   return 0; }  bool left(char a) {   if(a=='['||a=='(')return 1;   return 0; }  int main() {   int cas;   char s[200];   cin>>cas;   getchar(); while(cas--) { stack<char>q; gets(s);   if(strcmp(s,"/n")==0) {   cout<<"Yes"<<endl;   continue; }   for(int i=0;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 0; }

我自己的是下面这一种，可能更容易理解一些，也是栈的思想

#include<stdio.h> #include<string.h> int main() {   int i,T;   int flag;   int s[135],j,top;   char c[135];   scanf("%d",&T);   getchar(); while(T--) {   fgets(c,sizeof(c),stdin); //考虑空行（c:字符串，sizeof(c):字符串长度，stdin：从键盘输入）   flag=0;   j=0;   for(i=0; c[i]!='/n'; i++) {   if(c[i]=='(')     s[j++]=0;   else if(c[i]=='[')     s[j++]=1;   else if(c[i]==')') {   if(j!=0 && s[j-1]==0)     j--;   else   {     flag=1;     break;   } }   else if(c[i]==']') {   if(j!=0 && s[j-1]==1)     j--;   else   {     flag=1;     break;     }   }   else   {     flag=1;     break;   }   }     if(flag || j!=0) //栈中有剩余为No     printf("No/n");   else     printf("Yes/n");   }   return 0;   }