Flipped parentheses P64777


Statement
 

pdf   zip

html

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

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

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

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

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 104 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