A CME (Correct Mathematical Expression) was defined by the following rules:

`z`is a CME;- if
*X*is a CME, then so is`(`*X*`)`; - if
*X*and*Y*are both CMEs, then so is`(`*X*`+`*Y*`)`; - there are no more CMEs than those produced by the three rules above.

This set of rules produces terms like

Unfortunately, the job to produce the CMEs was given to a half-crazy computer (a
HAL’s cousin) that sometimes flipped the parentheses, from ‘`)`’ to
‘`(`’ and viceversa, thus producing terms like

We call these terms ACMEs (Almost Correct Mathematical Expressions). You are asked to write a program such that, given an ACME, computes the minimum number of parentheses that must be flipped to get a CME.

**Input**

The input has several non-empty strings consisting
of at most 10^{4} characters chosen from {‘`z`’, ‘`(`’, ‘`)`’, ‘`+`’}.

**Output**

For each string of the input, tell if it is a CME, an ACME, or rubbish. In the second case, compute the minimum number of flips to convert the string into a CME.

Public test cases

**Input**

z (z+(z+z() +z

**Output**

z : this is a CME (z+(z+z() : 1 flip(s) +z : this is rubbish

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Primer Concurs de Programació de la UPC - Final
- Date
- 2003-09-23