You will be given a String formula that adheres to the folowing pseudo-grammar (quotes for clarity):
<FORMULA> :== D(<FORMULA>) | I(<FORMULA>) | T(<NUM>,<FORMULA>) | 'f'
<NUM> :== a positive integer between 1 and 100 inclusive with no leading zeros
The following congruences allow us to change a formula into an equivalent one (here F denotes some <FORMULA>):
D(I(F)) == F
I(D(F)) == F
D(T(i,F)) == T(i-1,D(F))
I(T(i,F)) == T(i+1,I(F))
Return a String describing a formula equivalent to the input such that the total number of 'D's and 'I's is minimized. The returned value must be formatted like the input. If there are multiple possible return values, choose the one where no 'D' or 'I' could be nested deeper using a single congruence. Remember that any number in the returned value, as well as in any intermediate formulae, must be between 1 and 100, inclusive. |