673 - Parentheses Balance
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=614
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
技巧:在栈底加一个元素,减少代码量。
完整代码:
/*0.029s*/
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
stack<char> s;
char str[130];
int main(void)
{
int t;
scanf("%d", &t);
getchar();
while (t--)
{
gets(str);
int len = strlen(str);
if (len & 1)
puts("No");
else
{
if (!s.empty())
s.pop();
s.push('0');///“记号”
for (int i = 0; i < len; ++i)
{
if (str[i] == '(' || str[i] == '[')
s.push(str[i]);
else if (str[i] == ')')
{
if (s.top() == '(')
s.pop();
else
{
s.push('1');
break;
}
}
else/// ']'
{
if (s.top() == '[')
s.pop();
else
{
s.push('1');
break;
}
}
}
puts(s.top() == '0' ? "Yes" : "No");
}
}
return 0;
}