Statistics

Problem Statement for "MissingParentheses"

Problem Statement

Given a string of parentheses, you must turn it into a well formed string by inserting as few parentheses as possible, at any position (you cannot delete or change any of the existing parentheses).

A well formed string of parentheses is defined by the following rules:

  • The empty string is well formed.
  • If s is a well formed string, (s) is a well formed string.
  • If s and t are well formed strings, their concatenation st is a well formed string.
As examples, "(()())", "" and "(())()" are well formed strings and "())(", "()(" and ")" are malformed strings.

Given a String par of parentheses, return the minimum number of parentheses that need to be inserted to make it into a well formed string.

Definition

Class:
MissingParentheses
Method:
countCorrections
Parameters:
String
Returns:
int
Method signature:
int countCorrections(String par)
(be sure your method is public)

Constraints

  • par will contain between 1 and 50 characters, inclusive.
  • Each character of par will be an opening or closing parenthesis, i.e., '(' or ')'.

Examples

  1. "(()(()"

    Returns: 2

    The string below is a possible well formed string you can get to by inserting the two closing parentheses marked. (())(()) ^ ^

  2. "()()(()"

    Returns: 1

    You can fix the string by inserting a single closing parenthesis at the end.

  3. "(())(()())"

    Returns: 0

    The input string is well formed, so no insertion is needed.

  4. "())(())((()))))()((())))()())())())()()()"

    Returns: 7

  5. "()"

    Returns: 0

  6. ")(())((((()()())))(()(())((()(()(((())(()(((((()))"

    Returns: 12

  7. "())()))())()()()))())()()((()()())))(()()()()(()))"

    Returns: 8

  8. "())())(()(())()())())(()))))()()((((()()(())(()((("

    Returns: 14

  9. ")(()(()()()()())()(()(((())))()(((())))()))))())(("

    Returns: 6

  10. "()()()()())((()))()()()(())))))))(())))()((()()()("

    Returns: 12

  11. "(((()(((((()((((((((()((()(((((()(()(((()(((()()(("

    Returns: 32

  12. "((()((()(()()()()(((((((((((()()(((()((((((((()()("

    Returns: 28

  13. ")))((()()(()))())((())(()))))))())())()())))(((()("

    Returns: 16

  14. "()()()(())()))()))()))())))))(((())(())(()))))))))"

    Returns: 16

  15. ")(())()))()((())))))))()(())()))())())))()))))((()"

    Returns: 20

  16. "())((()))))()))))()()())))()(()()))()))))()))))())"

    Returns: 20

  17. "))))(((()(()(())())))))()))))))()))())(())(())))(("

    Returns: 18

  18. "()(((((((((((((((()(((((("

    Returns: 21

  19. "((((()((((((()((((()(((("

    Returns: 18

  20. ")))))))))))()"

    Returns: 11

  21. "()((((())"

    Returns: 3

  22. ")))("

    Returns: 4

  23. "(((((((((((((((((()))))))))))))))))"

    Returns: 1

  24. ")))))))))))))))))(((((((((((((((((("

    Returns: 35

  25. "(((((((((((((((()))))))))))))))))))))"

    Returns: 5

  26. ")))))))))))))))))))(((((((((((((((((("

    Returns: 37

  27. "(((((((((((((()))))))))))))"

    Returns: 1

  28. ")))))))))))(((((((((((((((("

    Returns: 27

  29. "((()(())()())((()())()()()()()()()()()()(()()())))"

    Returns: 0

  30. "(((((((((()()((())(()))()())()())()())))))(()())))"

    Returns: 0

  31. "(((((()))))()()(((((((((((((()))))(()())))))))))))"

    Returns: 0

  32. "(()))()()()()()(()(()()((())())()())()(())()()()()"

    Returns: 2

  33. "((((((())))))((((())()))((()()())((())(())()))))))"

    Returns: 2

  34. "(((((())(((()))))()((()))()()))))((()))(((((()))))"

    Returns: 2

  35. "((()((())())))()(((()()()()()())))()()(()()())()))"

    Returns: 2

  36. "(((()())()()))(()())((((())))()((())()))(())(()())"

    Returns: 0

  37. "((((((((()))((())()(((((())))))((((((())))))))))))"

    Returns: 2

  38. "(((())()()((((()()())(()))()()()()()(())())((())))"

    Returns: 2

  39. "())(())))((((((((())())()(((())((()()(())())))))))"

    Returns: 6

  40. "((((()))((())()))(((((()())()))(((((())))))((())))"

    Returns: 2

  41. "((()()(())(()()()()()()()(())())())())))"

    Returns: 2

  42. "(()(())(())))((()))(()(()(()))"

    Returns: 2

  43. "(((()))))(()((()))))"

    Returns: 2

  44. "()(()())((()))((()()()(())))((()))()(()())()()(())"

    Returns: 0

  45. "((()(())()(()()())(((())()(()()(()((()))())))))())"

    Returns: 0

  46. "((())(()((((((((())())))))(()))))(((((())()())))))"

    Returns: 0

  47. "())((()(()(())(()()))()()()()()()((())()()()()()))"

    Returns: 2

  48. "(()()()(()))((((())))((()()()()(())))()))(())))())"

    Returns: 4

  49. "(((((((((())))()))()))))((((((((()))())())))))))))"

    Returns: 4

  50. "((((()))())((()())))"

    Returns: 0

  51. "()(((((((()))))(((()))(())))))"

    Returns: 0

  52. "()(()((())))))(()())"

    Returns: 2

  53. "((())())()())(())((()()()())(((())))()))((())(()()"

    Returns: 4

  54. "(())((())()()))()()))())()())()())()()()()()()()()"

    Returns: 6

  55. "(()()()())((()(()))()())())()()()()()())((()()()()"

    Returns: 4

  56. "((((()()()(()))(((()))()(()())(())))(())))(())()))"

    Returns: 2

  57. "(()))(())(())())((()(()())())(())(()()()())()()(()"

    Returns: 4

  58. "((((((()))))))(((())))(()(((()))((((()()()))))((()"

    Returns: 4

  59. "(((())((((()(()()())))()()())()((()(())(())(((()))"

    Returns: 6

  60. "(((()))())()()(()))())(()())()(()))((())))()()())"

    Returns: 5

  61. "(((((((())))()))))()(()(()((())(((((())))(())))))"

    Returns: 1

  62. "(((()))(()(())((((()(()((())(((()))(((())((()))))"

    Returns: 9

  63. "(((())))((())(()))((()()()(()(((()()()())))(((())"

    Returns: 5

  64. ")()())(((()))()(()(()()())((())()(())((()))))(())"

    Returns: 3

  65. "(())(((()())(())()((())))()(()())(())()())())))))"

    Returns: 5

  66. "((())()))((())((((((())(((()))))))(()(()())))))))"

    Returns: 3

  67. "()()())((((()())))(()()))((()(()(()(())()(())()()"

    Returns: 5

  68. "(((((((((((((((((((((((((((((((((((((((((((((((((("

    Returns: 50

  69. "))))))))))))))))))))))))))))))))))))))))))))))))))"

    Returns: 50

  70. ")))))))))))))))))))))))))((((((((((((((((((((((((("

    Returns: 50

  71. ")))((("

    Returns: 6

  72. ")("

    Returns: 2

  73. "())("

    Returns: 2

  74. ")())(()(("

    Returns: 5

  75. ")))))((((("

    Returns: 10

  76. "()()((()())()((()()()()))))()()((()())()((()()()()"

    Returns: 4

  77. ")())))(((((()((((())((("

    Returns: 15

  78. ")(())("

    Returns: 2

  79. "()))))((((()"

    Returns: 8

  80. "()))((()"

    Returns: 4

  81. "))(("

    Returns: 4

  82. "()))))))((())(((((()()("

    Returns: 13

  83. ")(("

    Returns: 3

  84. ")()))((()("

    Returns: 6

  85. "))))(((()"

    Returns: 7

  86. "())(())((()))))()((())))()())())())()()()((("

    Returns: 10

  87. "))())))(((((("

    Returns: 11

  88. "(()())))(()"

    Returns: 3

  89. "((("

    Returns: 3

  90. "))("

    Returns: 3

  91. "))))))(("

    Returns: 8

  92. "())))(((("

    Returns: 7

  93. "())))("

    Returns: 4

  94. "(()))("

    Returns: 2

  95. "))))(())(()"

    Returns: 5

  96. ")))()()("

    Returns: 4

  97. "))))))))))))))))))))()))((((((((((()((((((((((((("

    Returns: 45

  98. "()))("

    Returns: 3

  99. ")))(("

    Returns: 5

  100. ")()()()("

    Returns: 2

  101. ")))()((("

    Returns: 6

  102. "((((())))))))))((((("

    Returns: 10

  103. ")((("

    Returns: 4

  104. "))))(())((((()"

    Returns: 8

  105. "))))(((("

    Returns: 8

  106. ")"

    Returns: 1

  107. ")()("

    Returns: 2

  108. ")))))))((())()(((())))()()("

    Returns: 9

  109. "())()("

    Returns: 2

  110. "))"

    Returns: 2

  111. "(())))(()))(((((((())"

    Returns: 9

  112. "))))(((((((((("

    Returns: 14

  113. "(()))((())"

    Returns: 2

  114. "("

    Returns: 1

  115. ")((()"

    Returns: 3

  116. ")))))))))(())))(((("

    Returns: 15

  117. ")())("

    Returns: 3

  118. "())"

    Returns: 1

  119. "))((("

    Returns: 5

  120. ")(()((((()))))))()()(()(()(())()()()))())("

    Returns: 4

  121. "())(()"

    Returns: 2

  122. "))))"

    Returns: 4

  123. "))))))))))))))))))((()))()(())(())(((((((((((((((("

    Returns: 34

  124. "(((((((((((((((((((("

    Returns: 20

  125. "))))))(((((("

    Returns: 12

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: