google_interviewsoltion_correctingstring.py

import math
'''
the solution , will use 2 stack and 2 counters
for each closing case and open case
and will flip each close case if no open case for it
'''

def correctstring(s):
    open_stack = []
    close_stack = []
    open_counter = 0
    close_counter = 0
    for ch in s:
        if ch == '(':
            # open case
            open_stack.append(ch)
            open_counter +=1
            close_counter -=1
        elif ch == ')':
            #close case
            if (len(open_stack) == len(close_stack) ) and (open_counter == 0) and (close_counter == 0):
                open_stack.append('(')
                open_counter +=1
                close_counter -=1
            else:
                close_stack.append(ch)
                close_counter +=1
                open_counter -=1
    while open_counter < 0:
        open_stack.append('(')
        open_counter +=1
    while close_counter < 0: 
        close_stack.append(')')
        close_counter +=1

    return ''.join(open_stack) + ''.join(close_stack)
  


# These are the tests we use to determine if the solution is correct.
# You can add your own at the bottom.

def printInteger(n):
  print('[', n, ']', sep='', end='')

test_case_number = 1

def check(expected, output):
  global test_case_number
  result = False
  if expected == output:
    result = True
  rightTick = '\u2713'
  wrongTick = '\u2717'
  if result:
    print(rightTick, 'Test #', test_case_number, sep='')
  else:
    print(wrongTick, 'Test #', test_case_number, ': Expected ', sep='', end='')
    printInteger(expected)
    print(' Your output: ', end='')
    printInteger(output)
    print()
  test_case_number += 1

if __name__ == "__main__":
  t_1 = "(()" 
  expected_1 = '(())'
  output_1 = correctstring(t_1)
  check(expected_1, output_1)

  t_2 = "(())))"
  expected_2 = '((()))'
  output_2 = correctstring(t_2)
  check(expected_2, output_2)