Brackets in a manuscript
An editor is proofreading an electronic manuscript and wants a program to show at once where brackets and quotes are mismatched. The pairs are ( ), [ ], { }, « » and „ “; the last are used for quotes within quotes. The placement is correct when each closing one closes the last still-open opening one of the same kind and nothing is left open at the end: («да») is correct, («да)» is not.
Find the first error. Three tests are real chapters of War and Peace (the Russian original) from the electronic text the site’s sandbox works with; one of them really does contain an error.
Input
Text in UTF-8, up to 10⁶ characters, over several lines. All characters other than the ten brackets listed are ordinary text.
Output
YES if the brackets are placed correctly. Otherwise NO p, where p is the number of the character with the error, counting from 1 and counting all characters, including spaces and line breaks. The error is the first closing bracket with nothing to close: no brackets are open, or the last open one is of another kind. If there are none such, but open ones remain at the end, the error is the very first of the remaining open ones.
Examples
Example 1
Он сказал («да» [и нет]) — и ушёл.
YES
Example 2
Наташа (как всегда «весело) ответила».
NO 27
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 11 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
If there were only one kind of bracket, a counter would do: plus one for an opening bracket, minus one for a closing one, and the counter must not go negative. Why are five counters not enough for five kinds? Look at the second example.
2Hint 2
A closing bracket must close the last open one. What data structure remembers what was opened last and can forget it quickly?
3The idea
A stack. An opening bracket goes on the stack along with its position. A closing one looks at the top: if the stack is empty or the top holds a bracket of another kind, that is the first error. Otherwise pop the top. If the text has ended and the stack is not empty, the error is its bottom: the earliest of the unclosed ones.
4Walkthrough
One pass over the text. The stack holds the positions of opening brackets; the kind is taken from the text by position (or stored alongside). The five counters from the first hint break on («)»: each kind on its own is balanced, but the brackets cross, and counters cannot see that.
On the third test the stack finds a real digitisation error: the hunting chapter has «как и всегда в (своих суждениях…» (“as always in (his judgements…”), and that bracket is not closed within the chapter. The article shows what such a bracket does to the whole novel: it is accidentally “closed” by the item number “1)” in the fourth volume, more than a million characters later. On the fifth test the error is formal: the “1)” in a list of Masonic virtues is a number, not a bracket, but by the rules of the problem it is a closing bracket without a pair. A real proofreading program would have to know about that too.
Positions are in characters, not bytes. In Python a string after decode is indexed by characters. In Go for _, ch := range s iterates over characters, but the first value returned is a byte index, and a Cyrillic letter takes two bytes in UTF-8; the number has to be counted separately.
4+Solution
5Complexity
O(n) time: each character is looked at once, and each bracket is pushed and popped at most once. Memory is O(n) in the worst case, when all brackets are opening ones.
6Common mistakes
- Counters instead of a stack. They miss crossed brackets, as in the second example.
- Recursion. The ninth test is a quarter of a million nested brackets: Python’s recursion depth will not suffice, but an explicit stack will.
- A byte number instead of a character number. In Go the index in a
rangeover a string is in bytes; on Cyrillic text the answer drifts by almost a factor of two. - The wrong unclosed one. If several brackets are open at the end, the first one (the bottom of the stack) is needed, not the last.