10906 - Strange Integration
The problem seems to me like the code-generating part of a compiler - generating expressions corresponding to an AST (Abstract Syntax Tree).
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.
- 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
Expression #1: 2+3+(2+3) Expression #2: 2+3+4+5