SHARE
TWEET

Untitled

a guest Jan 24th, 2020 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # Given a string of parentheses, find the balanced string that can be produced from it using the minimum number of insertions and deletions. If there are multiple solutions, return any of them.
  2.  
  3. # For example, given "(()", you could return "(())". Given "))()(", you could return "()()()()".
  4.  
  5. from collections import deque
  6.  
  7. def fix_paranthesis(seq: str):
  8.     new_seq = deque([])
  9.     count = 0
  10.     for p in seq:
  11.         if p == '(':
  12.             if count < 0:
  13.                 new_seq.extendleft('(' * (count * -1))
  14.                 count = 0
  15.             count += 1
  16.         if p == ')':
  17.             count -= 1
  18.         new_seq.append(p)
  19.     if count < 0:
  20.         new_seq.extendleft('(' * (count * -1))
  21.     elif count > 0:
  22.         new_seq.extend(')' * count)
  23.     return ''.join(new_seq)
  24.  
  25. test_cases = [
  26.     {
  27.         'input': '((',
  28.         'output': '(())',
  29.     },
  30.     {
  31.         'input': '(()',
  32.         'output': '(())',
  33.     },
  34.     {
  35.         'input': '))()(',
  36.         'output': '(())()()',
  37.     },
  38.     {
  39.         'input': '))()(()))))',
  40.         'output': '((((())()(()))))',
  41.     },
  42.     {
  43.         'input': '((((',
  44.         'output': '(((())))',
  45.     },
  46.     {
  47.         'input': '(((())()((',
  48.         'output': '(((())()(())))',
  49.     },
  50.     {
  51.         'input': '((())()(()))))',
  52.         'output': '((((())()(()))))'
  53.     },
  54.     {
  55.         'input': '',
  56.         'output': '',
  57.     },
  58.     {
  59.         'input': ')',
  60.         'output': '()',
  61.     },
  62.     {
  63.         'input': '(',
  64.         'output': '()',
  65.     },
  66.     {
  67.         'input': '()',
  68.         'output': '()',
  69.     },
  70.     {
  71.         'input': '()()()',
  72.         'output': '()()()',
  73.     }
  74. ]
  75.  
  76. def test():
  77.     for index, test_case in enumerate(test_cases):
  78.         print(f'Running test case {index + 1}')
  79.         assert fix_paranthesis(test_case['input']) == test_case['output']
  80.         print('OK')
  81.  
  82. test()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top