UVa 673

From Algorithmist

Contents 1 673 - Parentheses Balance 2 Summary 3 Explanation 4 Notes 5 Input 6 Output

[edit] 673 - Parentheses Balance

• http://acm.uva.es/p/v6/673.html

[edit] Summary

The task is to check whether a given string contains a properly nested set of parentheses.

Since the language described is a very simple context-free language, we can use a [[stack]] to implement the associated push-down automaton.

[edit] Explanation

The context-free language in question looks as follows:

S -> [S] | (S) | SS | nothing

[edit] Notes

Read the input line by line, the problem statement silently allows empty rows in the input.

[edit] Input

7
([])
(([()])))
([()[]()])()
(
(]
)(
][

[edit] Output

Yes
No
Yes
No
No
No
No