UVa 673 Parentheses Balance （栈）

UVa 673 Parentheses Balance （栈）2014-07-14 csdn博客 synapse7673 - 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

YesNoYes

技巧：在栈底加一个元素，减少代码量。

完整代码：

/*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;}