[Programmers/Python] 괄호 변환

def isBal(p):
    stack = []
    for letter in p:
        if letter == '(':
            stack.append(letter)
        else:
            if len(stack) == 0:
                return False
            else:
                stack.pop()
    
    if len(stack) == 0:
        return True
    else:
        return False
    
#2
def setUV(p):
    left, right = 0, 0
    for i in range(len(p)):
        if p[i] == '(':
            left += 1
        else:
            right += 1
    
        if left == right:
            u = p[:i+1]
            if i+1 > len(p):
                v = ''
            else:
                v = p[i+1:]
            break
                
    return u, v

def rules(p):
    result = ''
    #1
    if len(p) == 0:
        return ''
    
    #2
    u, v = setUV(p)
    
    #3
    if isBal(u) == True:
        result += u + rules(v)
        
    #4
    else:
        bracket = '(' #4-1
        bracket += rules(v) + ')' #4-2,3
        u = u[1:-1]
        
        #4-4
        for nu in u:
            if nu == '(':
                bracket += ')'
            else:
                bracket += '('
    
        result += bracket
    
    #4-5
    return result
            

def solution(p):
    answer = ''
    if isBal(p) == True:
        return p
    answer = rules(p)
    
    return answer

풀이과정

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.

0. 문제에서 주어진 과정을 그대로 구현하면 된다. (코드에 주석으로 해당 구현 표시함)

 

a. rules라는 주어진 과정을 구현하는 함수를 새로 만든다.

 

b. setUV라는 u,v를 분리하는 함수를 새로 만든다.

b-1. '('와 ')'의 개수를 각각 구해서, 개수가 같아지면 '균형잡힌 괄호 문자열'이므로 u, v로 나눈다.

        → index에러가 생기지 않게 주의하기

 

c. isBal라는 '균형잡힌 괄호 문자열'을 판별하는 함수를 새로 만든다.

c-1. u가 '균형잡힌 괄호 문자열'이라면, result에 u를 이어 붙이고, v는 재귀적으로 rules함수를 수행한다.

c-2. u가 '균형잡힌 괄호 문자열'이 아니라면,

      빈문자열 'bracket' 에 '('를 첫 번째 문자로 하고, v를 rules함수를 수행한 값과 ')'를 이어붙인다.

c-3. u의 양 끝 문자를 제거하고, 남은 문자열의 괄호의 방향을 뒤집어서 bracket에 이어 붙인다.

c-4. result에 bracket을 이어붙인 뒤 return한다.

 

d. solution함수에서 먼저 주어진 p가 '균형잡힌 괄호 문자열'인지 판별해, 맞다면 p를 그대로 return한다.

d-1. 아니라면, rules함수를 수행해 답을 구한다.

---