UVa 10906

From Algorithmist
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