31ος ΠΔΠ B' Φάση Λυκείου
Ισορροπημένες παρενθέσεις (cntbal)

Μία συμβολοσειρά αποτελούμενη από παρενθέσεις θα λέμε ότι είναι «ισορροπημένη» αν (α) όλες οι παρενθέσεις που ανοίγουν κλείνουν, και (β) δεν κλείνουν παρενθέσεις που δεν έχουν προηγουμένως ανοίξει. Για παράδειγμα:

η συμβολοσειρά (()) είναι ισορροπημένη
η συμβολοσειρά ()() είναι επίσης ισορροπημένη
η συμβολοσειρά (() δεν είναι ισορροπημένη, γιατί η πρώτη παρένθεση που ανοίγει δεν κλείνει ποτέ
η συμβολοσειρά ())( δεν είναι ισορροπημένη, γιατί η δεύτερη παρένθεση που κλείνει δεν έχει προηγουμένως ανοίξει
η συμβολοσειρά (()())() είναι ισορροπημένη

∆ίνεται μία συμβολοσειρά \(S\) αποτελούμενη από \(N\) χαρακτήρες, κάθε ένας από τους οποίους είναι είτε ‘(’ ή ‘)’. Η συμβολοσειρά \(S\) δεν είναι απαραίτητα ισορροπημένη. Μετρήστε πόσες υποσυμβολοσειρές (δηλαδή πόσα «κομμάτια» της \(S\)) είναι ισορροπημένα.

Πρόβλημα

Αναπτύξτε ένα πρόγραμμα σε μια από τις γλώσσες του IOI (PASCAL,C, C++, Java) το οποίο, αφού διαβάσει τη συμβολοσειρά \(S\), θα εκτυπώνει το πλήθος των ισορροπημένων υποσυμβολοσειρών της.

Αρχεία Εισόδου:

Τα αρχεία εισόδου με όνομα cntbal.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή υπάρχει ένας ακέραιος αριθμός \(N\) (όπου \(1 \leq N \leq 1.000.000\)), το πλήθος των χαρακτήρων της συμβολοσειράς. Η επόμενη γραμμή περιέχει τους \(N\) χαρακτήρες που αποτελούν τη συμβολοσειρά \(S\). Υποθέστε ότι η συμβολοσειρά αποτελείται μόνο από χαρακτήρες ‘(’ ή ‘)’.

Αρχεία Εξόδου:

Τα αρχεία εξόδου με όνομα cntbal.out είναι αρχεία κειμένου που αποτελούνται από μία μόνο γραμμή με έναν μόνο ακέραιο αριθμό: το πλήθος των ισορροπημένων υποσυμβολοσειρών της \(S\).

Παραδείγματα Αρχείων Εισόδου - Εξόδου:

Οι ισορροπημένες υποσυμβολοσειρές φαίνονται υπογραμμισμένες δεξιά.

1^o

cntbal.in	cntbal.out	Επεξήγηση:
5 ())()	2	())() -- --

2^o

cntbal.in	cntbal.out	Επεξήγηση:
8 (()(()))	5	(()(())) -- -- ---- ------ --------

3^o

cntbal.in	cntbal.out	Επεξήγηση:
3 ))(	0	δεν υπάρχει καμία ισορροπημένη υποσυμβολοσειρά

4^o

cntbal.in	cntbal.out	Επεξήγηση:
6 ()()()	6	()()() -- -- -- ---- ---- ------

Παρατηρήσεις: