首页 > 代码库 > UVA Parentheses Balance

UVA Parentheses Balance

题目如下:

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


这道题我用STL中的链表做的,主要是为了可以方便地删除元素。我的思路是只要遇到()或[]就把这两个元素删除了,层层“剥下去”,如果能够剥到链表为空,则YES,反之NO。一个细节是要注意迭代器变量的值,删除后迭代器指向下一个元素,所以要将它自减以免漏掉元素。还有判断相邻两个元素的时候,迭代器会自加,要及时自减。另一个细节是可能直接输入一个空字符串,所以提前还要判断一下,因为这个WA了一次QAQ。

AC的代码如下:

<script src="https://code.csdn.net/snippets/336544.js" type="text/javascript"></script>