[백준] 괄호 추가하기

https://www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

이 문제의 포인트는 중위 연산을 후위 연산으로 바꾸는 작업과 먼저 계산할 연산자를 정하는 것입니다. 현재 연산자를 괄호로 묶어서 먼저 계산할 경우에는 다음에 나오는 연산자는 먼저 계산할 수 없으므로 다다음 연산자로 넘겨야합니다. 이 문제에서 후위 연산자로 바꾼는 방법은 숫자는 나오는 순서대로 list에 넣어주고 연산자인 경우 현재 연산자가 먼저 계산되어야하면 스택에 먼저 계산되면 안되는 연산자가 나올때까지 스택에서 빼서 넣어주고 먼저 계산되면 안되는 연산자면 스택에 있는 모든 연선자를 스택에서 빼서 리스트에 넣어주면 됩니다.

 

import sys

n = int(input())
ex = list(input().rstrip())

prior = [False] * n

def calculate(order):
    stack = []
    for cur in order:
        if cur == '-' or cur == '+' or cur == '*':
            num1 = stack.pop()
            num2 = stack.pop()
            ret = 0

            if cur == '+':
                ret = num2 + num1
            elif cur == '-':
                ret = num2 - num1
            elif cur == '*':
                ret = num2 * num1

            stack.append(ret)

        else:
            stack.append(cur)

    return stack[0]


ans = -sys.maxsize

def subset(cnt):
    global ans

    if cnt >= n:
        order = []
        stack = []

        for i in range(n):
            # 현재가 숫자인 경우
            if i % 2 == 0:
                order.append(ord(ex[i]) - ord('0'))
            # 현재가 연산자인 경우
            else:
                if not stack:
                    stack.append(i)
                else:
                    if prior[i]:
                        while stack and prior[stack[-1]]:
                            order.append(ex[stack[-1]])
                            stack.pop()

                        stack.append(i)
                    else:
                        while stack:
                            order.append(ex[stack[-1]])
                            stack.pop()

                        stack.append(i)
        while stack:
            order.append(ex[stack[-1]])
            stack.pop()

        ret = calculate(order)
        ans = max(ans, ret)
        return

    prior[cnt] = True
    subset(cnt + 4)

    prior[cnt] = False
    subset(cnt + 2)

subset(1)
print(ans)