UVa 673

From Algorithmist
Jump to navigation Jump to search

673 - Parentheses Balance[edit]

Summary[edit]

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.

Explanation[edit]

The context-free language in question looks as follows:

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

Notes[edit]

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

Gotchas[edit]

There are spaces in the input consider it. For a C++ implementation, be careful to use 'cin.ignore' after reading the initial integer. Doing so will allow 'getline' to properly read the following strings, including the blank lines.

Input[edit]

8
([] )
(([()])))
([()[]()])()
(
(]
)(
][
([)]

Output[edit]

Yes
No
Yes
No
No
No
No
No

Solutions[edit]