[알고리즘] 백준 16637 괄호 추가하기 / python

www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

 

#스택에 숫자와 연산자를 넣어서 계산
def cal2(lst):
    op, num = [], []
    for i in lst[::-1]:
        if i == '+' or i == '-' or i == '*':
            op.append(i)
        else:
            num.append(int(i))
    while len(num) > 1:
        n1 = num.pop()
        n2 = num.pop()
        oper = op.pop()
        if oper == '+':
            num.append(n1 + n2)
        elif oper == '-':
            num.append(n1 - n2)
        elif oper == '*':
            num.append(n1 * n2)
    return num.pop()

#괄호있는 숫자는 미리 계산하고 리스트에 넣어서 cal2함수로 보냄 
def cal(cal_s):
    lst = []
    i = 0
    while i < len(cal_s):
        if cal_s[i] == '(':
            temp = str(cal_s[i+1]) + str(cal_s[i+3]) + str(cal_s[i+5])
            lst.append(str(eval(temp)))
            i += 7
            continue
        elif cal_s[i] != '#' and cal_s[i] != ')':
            lst.append(cal_s[i])
        i += 1
    return cal2(lst)

#괄호 추가, 삭제하면서 재귀적으로 함수를 호출
def sol(idx):
    global result
    for i in range(idx, len(S), 4):
        if i+6 >= len(S):
            continue
        S[i] = '('
        S[i+6] = ')'
        result = max(result, cal(S))
        sol(i+8)
        S[i] = '#'
        S[i+6] = '#'
    return result

N = int(input())
S = '#'
for i in input():
    S += i+'#'
S = list(S)
result = cal(S)
print(sol(0))