HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Linear Data structures: Stacks, Queues, Linked Lists, etc > problem:


50262 - Brackets

Guest
• Discussion of problem (4)

Section problems

• 50262 - Brackets
• 50291 - Postfix Arithmetic Expressions
• 50286 - Remove Duplicates
• 50775 - Balanced Parenthesis
• 50340 - Game 19
• 50877 - Friendly Queue
• 51086 - Top popular student
• 50774 - Hot Potato
• 50777 - Dwarfs Maze

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Автор: Павел Кузнецов, ПГУ.

Correct bracket expression (CBE below) can be defined in the following way:

1. () - CBE
2. If A is CBE, then (A) is also CBE
3. If both A and B are CBE, then AB is also CBE

For example, (()()) is CBE, while ())( is not.

One can see from the above, that each opening bracket has a corresponding closing bracket. A pair from the opening bracket and corresponding closing bracket shallbe called block. You are given a correct bracket expression. Your task is to find the number of different block pairs, such that one block lies inside another.

Input
The first row of input file contains CBE. It's length does not exceed one million of symbols.
Output
Output one number - the amount of block pairs in the given CBE, such that one block lies inside another.

Input 1 Output 1 Input 2 Output 2 Input 3 Output 3 Input 4 Output 4
()()()
0
()(())
1
(()())
2
((()))
3

Для отправки решений необходимо выполнить вход.

www.contester.ru