大样例下载

【题目描述】

有一棵圣诞树，是一棵二叉树，每个结点要么没有儿子（即叶结点），要么恰好有两个儿子。

在有些叶结点上挂着苹果，一个叶结点上最多挂着一个苹果。

为了使圣诞树看起来更美观，你决定将一些叶结点上的苹果移动到其他叶结点上。同样地，一个叶结点最多只能挂一个苹果。

你希望对于树上的每个结点，它的左右儿子子树中包含的苹果的数量差不超过 $1$.

问：你最少需要移动多少个苹果？如果不可能完成，输出 -1.

多组数据。

【输入格式】

多组数据，每组数据占一行，包含一个字符串，用括号表示法描述一棵二叉树，其中 () 表示一个没有挂苹果的叶结点，(A) 则表示一个挂着苹果的叶结点。数据保证每组数据字符串中包含的 A 的数量均不超过 1000。

【输出格式】

每组数据的答案占一行。

【样例输入】

((A)())
((((A)(A))((A)()))(A))
(()(((A)(A))(A)))

【样例输出】

0
-1
1

【样例解释】

【数据范围】

30% 的数据：每个测试点不超过 10 组数据，每组数据中含有的 A 的数量不超过 5。

100% 的数据：每个测试点不超过 100 组数据，每组数据中含有的 A 的数量不超过 1000。