# UVa 10906

Jump to navigation
Jump to search

## 10906 - Strange Integration[edit]

## Summary[edit]

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

## Explanation[edit]

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[edit]

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

## Input[edit]

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

## Output[edit]

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