Stable String

Time limit1sMemory limit128 MB

Summary

Given a string of braces, find the minimum number of single-character flips that make all brackets correctly balanced.

Level: Medium4 of 10
Topics: Stack, Greedy, Implementation, String
Solved: No attempts yet

Problem

You are given a string consisting only of the opening brace { and the closing brace }. Find the minimum number of operations needed to turn it into a stable string.

A stable string is defined as follows.

The empty string is stable.
If a string $S$ is stable, then $\{S\}$ is also stable.
If strings $S$ and $T$ are stable, then their concatenation $ST$ is also stable.

For example, {}, {}{}, and {{}{}} are stable, while }{, {{}{, and {}{ are not.

Two operations may be applied to the string:

Change an opening brace { into a closing brace }.
Change a closing brace } into an opening brace {.

Input

The input consists of several data sets. Each data set is a single line containing a string made up only of the opening brace { and the closing brace }. Each string is at most $2000$ characters long, and its length is always even.

The last line of the input contains one or more hyphens -; this line is not processed.

Output

Print one line for each data set. Each line contains the number of the data set (starting from $1$ , numbered in the order the data sets appear) and the minimum number of operations needed to make its string stable, in the format number. count.

Examples1

Example 1
Input
```
}{
{}{}{}
{{{}
---
```
Expected output
```
1. 2
2. 0
3. 1
```