• Python algorithm question
  • Stack question
  • find the minimum number of parentheses that should be added to make the input string valid
  • for example:
    • if s = "()", then the solution should return 0, since no parenthesis needs to be added to make s valid
    • if s = "(", then the solution should return 1, since one parenthesis (a right one) needs to be added to make s valid (s = "()")
    • if s = ")(", then the solution should return 2, since two parentheses (a left and a right) need to be added to make s valid (s = "()()")
  • the parentheses are valid if they are always in pairs and in the correct order
  • assume the string only includes '(' and ')'
  • find the solution with the complexity below,
• Complexity:
  • O(n) time
  • O(n) space

======================================================================

# implementation here

def exr_1(s): """ Find the minimum number of parentheses that should be added to make the input string valid The parentheses are valid if they are always in pairs and in correct order You may assume the string only includes '(' and ')' Parameters ---------- s: a string Returns ---------- the minimum number of parentheses that should be added: an integer """

===================================================================

# The output is given,

# Test s_1 = "()" s_2 = "(" s_3 = ")" s_4 = ")(" s_5 = "()()" s_6 = "))(("

print(exr_1(s_1)) print(exr_1(s_2)) print(exr_1(s_3)) print(exr_1(s_4)) print(exr_1(s_5)) print(exr_1(s_6))

0 1 1 2 0 4