UVa 10454

From Algorithmist
Jump to navigation Jump to search

Problem Number - Problem Name[edit]

Summary[edit]

How many distinct ways an expression consisting of operands, operator '+', operator '*' and parenthesis, can be correctly evaluated.

Explanation[edit]

Let be an expression with expressions as the operands and only one kind of operator (with loss of generality, the plus operator will be used):

Let be the number of ways an expression can be evaluated.

The answer for an expression with only one operand and no operators is trivial:

To evaluate , one can choose any of the operators to be the last one to be evaluated. If one choose the operator, there will be .

Therefore, .

As you may be familiar with, this is the famous Catalan number.

Extending this idea for general expression with sub-expressions, it's easy to see that the recursive Catalan idea maintains, only being multiplied by the answers of the sub-expressions. It only rests parse the input expression to oblige the precedence constraints and multiply for each "level" the Catalan number corresponding to the number of operands in the expression and the answers of the sub-expressions.

Notes[edit]

  • An expression is correctly evaluated if the evaluation steps do not violate any precedence constraints. It does not matter the operands values.

Optimizations[edit]

Pre calculate Catalan numbers.

Input[edit]

1+2+3+4
(1+2)+(3+4)
1+2+3*4
1+2+(3*4)

Output[edit]

5
1
2
2