Common Subexpression Elimination

Time limit1sMemory limit128 MB

Summary

Compress a labeled binary expression tree into a minimal DAG by merging identical subexpressions and print it with backreference numbers to earlier nodes.

Level: Medium6 of 10
Topics: Hash map, Tree, String, DFS
Solved: No attempts yet

Problem

Let the set $\Sigma$ consist of all words made of 1 to 4 lowercase letters, such as a, b, f, aa, fun, and kvqf. For any symbol $f \in \Sigma$ , expressions are built with the two grammar rules

$E \rightarrow f$
$E \rightarrow f(E,E)$

Every expression corresponds to a tree that mirrors its syntax. For example, the expression

a(b(f(a,a),b(f(a,a),f)),f(b(f(a,a),b(f(a,a),f)),f))

corresponds to a tree with $21$ nodes.

We can shrink this representation by using a graph (a directed acyclic graph) instead of a tree, so that identical subexpressions are stored once and shared. The expression above can be represented by such a graph with only $7$ nodes.

Because a tree is itself a graph, the graph representation is not unique. Given an expression, find a graph that represents it using as few nodes as possible.

Input

The first line contains an integer $c$ ( $1 \le c \le 200$ ), the number of expressions. Each of the next $c$ lines contains one expression written according to the grammar above, with no whitespace. The tree representation of each expression contains at most $50000$ nodes.

Output

For each expression, print one line containing a graph representation that uses as few nodes as possible.

The graph representation is written as a string by replacing repeated subexpressions with numbers. Each number refers to the root node of the subexpression that must be inserted at that position. Nodes are numbered sequentially starting from $1$ , in the order they are first written down; this numbering counts only the nodes that actually appear in the graph, not the occurrences that were replaced by a number. A number may only refer to a node written down earlier, so there are no forward references.

For the example expression a(b(f(a,a),b(f(a,a),f)),f(b(f(a,a),b(f(a,a),f)),f)), the answer is a(b(f(a,4),b(3,f)),f(2,6)).

Examples7

Example 1

Input

3
this(is(a,tiny),tree)
a(b(f(a,a),b(f(a,a),f)),f(b(f(a,a),b(f(a,a),f)),f))
z(zz(zzzz(zz,z),zzzz(zz,z)),zzzz(zz(zzzz(zz,z),zzzz(zz,z)),z))

Expected output

this(is(a,tiny),tree)
a(b(f(a,4),b(3,f)),f(2,6))
z(zz(zzzz(zz,z),3),zzzz(2,5))

Example 2
Input
```
1
a
```
Expected output
```
a
```
Example 3
Input
```
1
f(a,b)
```
Expected output
```
f(a,b)
```
Example 4
Input
```
1
f(a,a)
```
Expected output
```
f(a,2)
```
Example 5
Input
```
1
g(f(a,a),f(a,a))
```
Expected output
```
g(f(a,3),2)
```

Example 6

Input

1
k(k(k(a,a),k(a,a)),k(k(a,a),k(a,a)))

Expected output

k(k(k(a,4),3),2)

Example 7
Input
```
3
a
f(a,b)
z(z,z)
```
Expected output
```
a
f(a,b)
z(z,2)
```