TaylorAlgebra

TCO06 Semi 3 · 2006-03-01 · by AdminBrett

TCO06 Semi 3 · 2006-03-01 · by AdminBrett · String Parsing

Show categories

Class Name: TaylorAlgebra

Return Type: String

Method Name: getCanonical

Arg Types: (string)

Problem Statement

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.

Constraints

formula will contain between 1 and 50 characters, inclusive.
formula will adhere to the grammar in the statement.

Examples

"T(100,f)"
Returns: "T(100,f)"

None of the congruences are appropriate.

"D(T(50,f))"
Returns: "T(49,D(f))"

The 'D' can be nested more deeply.

"D(T(1,f))"
Returns: "D(T(1,f))"

We want to push the 'D' inward, but that would drop the number lower than 1.

"I(T(100,f))"
Returns: "I(T(100,f))"

Pushing the 'I' inward would force the number above 100.

"D(T(40,I(f)))"
Returns: "T(39,f)"

Submissions are judged against all 35 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TaylorAlgebra with a public method string getCanonical(string formula) · 35 test cases · 2 s / 256 MB per case