400396: GYM100162 C Expression with Sets

Expression with sets is an expression which has as operands some sets of integers between 0 and 999 999 999, inclusive. More formally, all these sets are subsets of the universal set U = {x: 0 ≤ x < 10⁹}. In the expression, each set is denoted as a possibly empty list of different integers separated with commas (","). Every such list is enclosed in braces ("{" and "}"). For example, these are valid sets: "{}", "{0}", "{1,2,3,4}", "{999999999,9,3}".

There are three possible operations with sets:

• Complement. Denoted as "!". For any set , we have . For example, !{1,5,2}={0,3,4,6,7,8,...,999999999}.
• Intersection. Denoted as "&". For any two sets , we have . For example, {0,1,2,3,4}&{1,5,2}={1,2}.
• Union. Denoted as "|". For any two sets , we have . For example, {0,1,2,3,4}|{1,5,2}={0,1,2,3,4,5}.

Here, the operations are listed in order from the highest priority to the lowest priority. The expression may also contain some brackets ("(" and ")"). Note that according to operations' priorities, A|!B&C = A|((!B)&C).

You are given an expression with sets. Evaluate it and print the number of elements in the resulting set.

The input contains several test cases. Each test case is a single line which is a single expression with sets. The length of the expression is between 1 and 10⁷ characters. The total number of operations (i.e. the number of characters "!", "&", "|") does not exceed 10⁶.

It is guaranteed that every expression is valid (i.e. it satisfies all the above descriptions) and the input doesn't contain any spaces.

For each test case, display the case number and the number of elements in the resulting set.

!{1,5,2}
{0,1,2,3,4}&{1,5,2}
{0,1,2,3,4}|{1,5,2}
!{1,2,3}|({1})
({1}|{2})&{1}

Case 1: 999999997
Case 2: 2
Case 3: 6
Case 4: 999999998
Case 5: 1