# UVa 10454

## Summary

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

## Explanation

Let ${\displaystyle E(n)}$ be an expression with expressions as the operands ${\displaystyle x_{i},\ 1\leq i\leq n}$ and only one kind of operator (with loss of generality, the plus operator will be used): ${\displaystyle E(n)=x_{1}+x_{2}+x_{3}+...+x_{n}}$

Let ${\displaystyle f(n)}$ be the number of ways an expression ${\displaystyle E(n)}$ can be evaluated.

The answer for an expression with only one operand and no operators is trivial: ${\displaystyle f(0)=1}$

To evaluate ${\displaystyle E(n),\ n>0}$, one can choose any of the ${\displaystyle n}$ operators to be the last one to be evaluated. If one choose the ${\displaystyle i-th}$ operator, there will be ${\displaystyle f(i-1)*f(n-i)}$.

Therefore, ${\displaystyle f(n)=\sum _{i=1}^{n}f(i-1)*f(n-i)}$.

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

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

## Optimizations

Pre calculate Catalan numbers.

## Input

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


## Output

5
1
2
2