# UVa 10906

## Summary

The problem seems to me like the code-generating part of a compiler - generating expressions corresponding to an AST (Abstract Syntax Tree).

## Explanation

Generating expressions from an AST is basically a recursive process. Brackets placing is the only hard part of the problem. Each node in the AST corresponds to an expression. Let x be a node and its corresponding expression be Expr(x). Then obviously, no brackets is needed for Expr(x) if

• x is the root of the AST;
• x is a leaf, i.e. Expr(x) is a number.

For the other nodes, brackets are needed if the following conditions hold.

• x is a right child and Expr(x) is of the same type ("+" or "*") as Expr(parent[x]), e.g. 1+(2+3).
• Expr(x) is of the type that has lower precedence than that of Expr(parent[x]), e.g. (1+2)*3.

## Gotchas

• The root of the AST is the last expression in each test case.

```2
2
A = 2 + 3
B = A + A
3
A = 2 + 3
B = A + 4
C = B + 5
```

## Output

```Expression #1: 2+3+(2+3)
Expression #2: 2+3+4+5
```