Parentheses Balance
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
题意:给一堆括号,让你判断是否能够组合
就是简单的栈的利用,把左半边的括号入栈,遇到右半边与其匹配。不过要注意到最后要判断是否为空栈。还有就是字符串当中可能有空格。
#include<iostream> #include<cstdio> #include<cmath> #include<stack> #include<cstring> using namespace std; int main () { int n,len,i; char str[130],temp; cin>>n; getchar(); while(n--) { bool flag=true; stack<char> s; gets(str); len=strlen(str); for (i=0; i<len; i++) if (str[i]==' ') ; else { if (!flag) break; if (str[i]=='(' || str[i]=='[') s.push(str[i]); else { if (s.empty()) { flag=false; break; } else { temp=s.top(); s.pop(); if ((str[i]==')' && temp=='(') || (str[i]==']' && temp=='[' ) ) ; else { flag=false; break; } } } } if (!s.empty()) flag=false; if (flag) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }