Statistics

Problem Statement for "BracketExpressions"

Problem Statement

We have three types of brackets: "()", "[]", and "{}". We are now interested in some special strings. A string is special if all the following conditions hold:

  • Each character of the string is one of the six bracket characters mentioned above.
  • The characters of the string can be divided into disjoint pairs such that in each pair we have an opening bracket and a closing bracket of the same type.
  • For each pair, the opening bracket must occur to the left of the corresponding closing bracket.
  • For each pair, the substring strictly between the opening and the closing bracket must be a special string (again, according to this definition).

For example, the empty string is a special string: there are 0 pairs of brackets. The string "[]" is also a special string: there is one pair of matching brackets, they are in the proper order, and the string between them (which is the empty string) is a special string.

The character 'X' (uppercase x) occurs in expression at most five times; all other characters in expression are brackets of the types mentioned above. We want to change expression into a special string by changing each 'X' into one of the brackets. (Different occurrences of 'X' may be changed into different brackets.) Return "possible" (quotes for clarity) if we can do that, and "impossible" otherwise.

Definition

Class:
BracketExpressions
Method:
ifPossible
Parameters:
String
Returns:
String
Method signature:
String ifPossible(String expression)
(be sure your method is public)

Constraints

  • expression will have between 1 and 50 characters, inclusive.
  • Each character in expression will be '(', ')', '[', ']', '{', '}' or 'X'.
  • There will be at most 5 occurences of 'X' in expression.

Examples

  1. "([]{})"

    Returns: "possible"

    This is already a special string. As there are no 'X's, we do not get to change anything.

  2. "(())[]"

    Returns: "possible"

  3. "({])"

    Returns: "impossible"

  4. "[]X"

    Returns: "impossible"

    Regardless of bracket type you put instead of 'X', you cannot create a special string.

  5. "([]X()[()]XX}[])X{{}}]"

    Returns: "possible"

    You can replace 'X's respectively with '{', '(', ')' and '['.

  6. "[{()}]("

    Returns: "impossible"

  7. "((())]"

    Returns: "impossible"

  8. "()}{[]"

    Returns: "impossible"

  9. "([)]"

    Returns: "impossible"

  10. "(][)"

    Returns: "impossible"

  11. "([[]]{[]}"

    Returns: "impossible"

  12. "()XX{}[["

    Returns: "impossible"

  13. "[{[{X]]}"

    Returns: "impossible"

  14. "(((((((((((([()X)))))))))))"

    Returns: "impossible"

  15. "(X{[X(()X"

    Returns: "impossible"

  16. "X{}[]()]X{X{}]X]"

    Returns: "possible"

  17. "{[]{}XX[])()[]{}"

    Returns: "possible"

  18. "(([])[])((){}){}"

    Returns: "possible"

  19. "{[[X[X[XX[[[[X[[[[[[[[{[()]}]]]]]]]]]]]]]]]]]])]]}"

    Returns: "possible"

  20. "[[{}{X[]][X][{()(){}[]}[(X[{}{}X()()][{}X{[]}()]()"

    Returns: "possible"

  21. "X[()X}]()[]}[{[]{()}()X[{}[]][{()}()()][X][]{}{}(X"

    Returns: "possible"

  22. "({[((X{}{}){}{X}(){}X[][]]XX{}{}}()}{}{}}{}[])[][]"

    Returns: "possible"

  23. "[({}[]{X){}[](X][][]{})()X[(){()}[XX}{}]{{()}()}()"

    Returns: "possible"

  24. "({[{{}{X}()](){}X[]({{[]}()}{}{{}()}{})[{}()]XXX[]"

    Returns: "possible"

  25. "XXX]][[][()]{}XX]]{}[]][()[]][][]){{[]{}}(){}}[]()"

    Returns: "possible"

  26. "{{{{[()[]][]}{}{XX{{}}(XXX{}{[]}{}]{}[]{{(){}}[]}}"

    Returns: "possible"

  27. "[({([])X{}[])[]X({()[]}[X[])[]())(X][][()[]()][]()"

    Returns: "possible"

  28. "[{()}(X{}{})(){X}X}}X])[[{}()X()[]([][][]){}()]{}]"

    Returns: "possible"

  29. "({}()[])(({}{})[]([()]()){()()[]}[][]){()()}[]{}[]"

    Returns: "possible"

  30. "[[[X[[[[X[[[[[X[[[[[X[[[[[[[[[[[[X[[[[[[[[[[[[[[[["

    Returns: "impossible"

  31. "(((((XXXX]"

    Returns: "impossible"

  32. "(X{{{{{{{{{{}}}}}}}}}}"

    Returns: "possible"

  33. "(X{{{{{{{{{{}}}}}}}}}}))"

    Returns: "possible"

  34. "(X{{{{{{{{{}}}}}}}}})}"

    Returns: "impossible"

  35. "([{X}])X"

    Returns: "impossible"

  36. "XXX[]()[{()()}][])]}"

    Returns: "possible"

  37. "(X)]"

    Returns: "impossible"

  38. "((((((XXXX"

    Returns: "impossible"

  39. "XXXX"

    Returns: "possible"

  40. "XXX"

    Returns: "impossible"

  41. "XXX[][]()]}"

    Returns: "impossible"

  42. "([}((XXX"

    Returns: "impossible"

  43. "X(X[X)X}"

    Returns: "possible"

  44. "X(([((X))]))"

    Returns: "impossible"

  45. "(XXXX]"

    Returns: "possible"

  46. "(X(X(X(X(X[]{}((()))"

    Returns: "possible"

  47. "[X]}"

    Returns: "impossible"

  48. "{[]X{[X]]}}XXX]{}{[[]]}{}{}{}{}{}{}{[][][]()()}}"

    Returns: "possible"

  49. ")("

    Returns: "impossible"

  50. "X(((XX"

    Returns: "impossible"

  51. "((X))"

    Returns: "impossible"

  52. "XX()[]}}"

    Returns: "possible"

  53. "X[XX(X"

    Returns: "possible"

  54. ")X"

    Returns: "impossible"

  55. ")"

    Returns: "impossible"

  56. "(X})X()X)(){}X"

    Returns: "possible"

  57. "[[X]"

    Returns: "possible"

  58. "({)}"

    Returns: "impossible"

  59. "[][]{}((X)(X()))[[X]]]{{X}}}[[]]"

    Returns: "possible"

  60. ")XX("

    Returns: "impossible"

  61. "(XXXXX)"

    Returns: "impossible"

  62. "[[[X]]"

    Returns: "possible"

  63. "{X]}"

    Returns: "possible"

  64. "XXX((("

    Returns: "impossible"

  65. "X(()"

    Returns: "impossible"

  66. "([]()[()]XX}[]){{}}]"

    Returns: "impossible"

  67. "()()X("

    Returns: "impossible"

  68. "{(X}"

    Returns: "possible"

  69. "XXXX()()()()()()()()()()()()()()()()()()()()()()(X"

    Returns: "possible"

  70. ")XXX"

    Returns: "impossible"

  71. "[X[]}]X}X]"

    Returns: "possible"

  72. "}"

    Returns: "impossible"

  73. "(((XXX"

    Returns: "possible"

  74. "[{]}"

    Returns: "impossible"

  75. "{{"

    Returns: "impossible"

  76. "X{"

    Returns: "impossible"

  77. "}{"

    Returns: "impossible"

  78. "(X{}"

    Returns: "possible"

  79. "(X"

    Returns: "possible"

  80. "X("

    Returns: "impossible"

  81. "XX"

    Returns: "possible"

  82. "XXXXX"

    Returns: "impossible"

  83. "[{[XX}"

    Returns: "impossible"

  84. "((([[())))XX"

    Returns: "impossible"

  85. "{(})"

    Returns: "impossible"

  86. "([X])X"

    Returns: "impossible"

  87. "{)"

    Returns: "impossible"

  88. "]XXX"

    Returns: "impossible"

  89. "(([)])"

    Returns: "impossible"

  90. "(X)}"

    Returns: "impossible"

  91. "{[}]"

    Returns: "impossible"

  92. "XX(("

    Returns: "impossible"

  93. "(X])"

    Returns: "possible"

  94. "([(]))"

    Returns: "impossible"

  95. "()X("

    Returns: "impossible"

  96. "X(})"

    Returns: "impossible"

  97. "([(])X"

    Returns: "impossible"

  98. "XXXXX)"

    Returns: "possible"

  99. "X}"

    Returns: "possible"

  100. "(("

    Returns: "impossible"

  101. "(((X"

    Returns: "impossible"

  102. "X["

    Returns: "impossible"

  103. "(X))"

    Returns: "possible"

  104. "([X]})"

    Returns: "impossible"

  105. "(XX]"

    Returns: "possible"

  106. "({X)"

    Returns: "possible"

  107. "{X"

    Returns: "possible"

  108. "XX]]"

    Returns: "possible"

  109. "XX{"

    Returns: "impossible"

  110. "[X])"

    Returns: "impossible"

  111. "{(XX)}"

    Returns: "possible"

  112. "[{(})][({})]"

    Returns: "impossible"

  113. "{X)}"

    Returns: "possible"

  114. "(X{X})"

    Returns: "possible"

  115. "[(X]"

    Returns: "possible"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: