BOJ [후위표기식]

문제

2022-03-25

문제보기

수식이 주어졌을때 해당 수식을 다음과 같이 후위표기식으로 바꾸는 문제이다.

풀이

노가다성으로 풀긴했는데 그다지 좋은 방법이 아니었다. 괄호때문에 아주 코드가 복잡해진다.

종회형 말처럼 일단 몇가지 예시를 스스로 끄적여 보면서 아이디어를 떠올려보자.

이러면 되지 않을까 하고 검증하고 바꾸고 식으로...

아이디어

피연산자는 answer에 이어 붙이고 연산자가 들어오면 [규칙]에 따라 진행

[규칙]

사칙연산이면 stack의 맨 위의 연산자가 본인보다 우선순위가 낮은애면

stack에 그대로 추가, 본인과 같거나 높을 경우 pop해서 answer에 붙임.

괄호가 나올경우 ( 는 스택에 추가, )는 ( 가 나올 때 까지 pop해서 answer에

붙임, 사칙연산이 나왔는데 맨위 원소가 ( 면 그냥 stack에 push

코드

exp = list(input())

index = 0
stk = []
to_check = []

def makeGroup(a,b):
    global stk, to_check, exp
    index = a
    count = 0
    while index < b+1-(count*2):
        
        if exp[index] == '*' or exp[index] == '/':
            count += 1
            temp_exp = "("+"".join(exp[index-1:index+2])+")"
            exp[index-1] = temp_exp
            for _ in range(2):
                del exp[index]
            index -= 1
        index += 1
            
    index = a

    while index < b+1-(count*2):

        if exp[index] == '+' or exp[index] == '-':
            count += 1
            temp_exp = "("+"".join(exp[index-1:index+2])+")"
            exp[index-1] = temp_exp
            for _ in range(2):
                del exp[index]
            index -= 1
        index += 1
    return a,b-(count*2)

for _ in range(len(exp)):   

    if exp[index] == "(":
        stk.append(index)
        

    elif exp[index] == ")":
        index2 = stk.pop()
        a,b = makeGroup(index2+1,index-1)
        temp_exp = "".join(exp[index2+1:b+1])
        exp[index2] = temp_exp
        for _ in range(b+1-index2):
            del exp[index2+1]
        index = index2
        to_check.append(index2)

    index += 1

makeGroup(0,len(exp)-1)

exp = list(exp[0])
stk = []
index = 0

for _ in range(len(exp)):
    if exp[index] == "(":
        stk.append(index)
    elif exp[index] == ")":
        start = stk.pop()
        temp = exp[start+2]
        exp[start+2] = exp[start+3]
        exp[start+3] = temp
        exp[start] = "".join(exp[start+1:start+4])
        for _ in range(4):
            del exp[start+1]
        index -= 4
    index += 1

print(exp[0])