[백준] 1918번: 후위표기식 - 파이썬

😀 서론

사실 저번주에 후위표기식 관련 문제를 풀었었다. 요기!
개념은 이해했으니 날로먹을 생각으로 골드 3에 도전했다가 보기좋게 실패했다ㅎ.ㅎ

위의 문제하고 이번 문제의 차이점은 순서이다. 후위 표기식2번 문제는 후위표기식을 중위표기식으로 바꾸어 값을 계산하는 거였다면, 이번 문제는 중위표기식을 후위표기식으로 바꾸기만 하면 되는 것이었다!

중위표기식을 후위표기식으로 변경
후위표기식을 중위표기식으로 바꾸고 값을 출력

이렇게 봤을 때 후자가 더 어려울 것 같지만,, 중위표기식을 후위표기식으로 바꾸려면 괄호치는 작업을 해야한다.
이게 난관이었다...

 

 

[백준] 1935번: 후위 표기식2 - 파이썬

 

📕 문제 풀이

1. 곱하기와 나누기가 우선순위가 높으니 괄호를 씌어준다.
2. 더하기와 뺴기에 괄호를 씌어준다.
3. 중위 표기식을 후위 표기식으로 바꿔준다. 자세한 내용은 위에 글 참조..

 

💻 실패코드!

sick = list(input())
#print(sick)
stk = []
first = {"*", "/"}
second = {"+","-"}
gualho = []
backtrack = [] # 뒤로 갈때 괄호 체크
some = []
result = []
check = False
check2 = False

c1 = sick.count("+") + sick.count("-") + sick.count("*") + sick.count("/")
c2 = sick.count("(")

if c1 != c2:
    for i in sick:
        if i == "(":
            gualho.append(i)
        elif i == ")":
            gualho.pop()

        if i in first:
            a = stk.pop()
            if a == ")":
                backtrack.append(a)
                some.append(i)
                some.append(a)
                while backtrack:
                    b = stk.pop()
                    some.append(b)
                    if b == ")":
                        backtrack.append(b)
                    elif b == "(":
                        backtrack.pop()
                some.append("(")
                some = some[::-1]
                stk.extend(some)
                some = []
                check2 = True

            else:
                stk.append("(")
                stk.append(a)
                stk.append(i)
                check = True
        elif check2 == True and i == ")" and len(gualho) == 0:
            stk.append(i)
            stk.append(")")
            check2 = False
        elif check2 == True and 65 <= ord(i) <= 90 and len(gualho) == 0:
            stk.append(i)
            stk.append(")")
            check2 = False
        elif i not in first and check == True and len(gualho) == 0:
            stk.append(i)
            stk.append(")")
            check = False
        elif i not in first and check == True and len(gualho) != 0:
            stk.append(i)
        elif i not in first and check == False:
            stk.append(i)

    result = stk.copy()
else:
    result = sick

gualo_cnt = stk.count("(")
yensan_cnt = stk.count("+") + stk.count("-") + stk.count("*") + stk.count("/")

sick = stk.copy()
stk = []

if gualo_cnt != yensan_cnt:
    for i in sick:
        if i == "(":
            gualho.append(i)
        elif i == ")":
            gualho.pop()

        if i in second:
            a = stk.pop()
            if a == ")":
                backtrack.append(a)
                some.append(i)
                some.append(a)
                while backtrack:
                    b = stk.pop()
                    some.append(b)
                    if b == ")":
                        backtrack.append(b)
                    elif b == "(":
                        backtrack.pop()
                some.append("(")
                some = some[::-1]
                stk.extend(some)
                some = []
                check2 = True
            else:
                stk.append("(")
                stk.append(a)
                stk.append(i)
                check = True
        elif i in first:
            stk.append(i)
        elif check2 == True and i == ")" and len(gualho) == 0:
            stk.append(i)
            stk.append(")")
            check2 = False
        elif check2 == True and 65 <= ord(i) <= 90 and len(gualho) == 0:
            stk.append(i)
            stk.append(")")
            check2 = False
        elif i not in first and check == True and len(gualho) == 0:
            stk.append(i)
            stk.append(")")
            check = False
        elif i not in first and check == True and len(gualho) != 0:
            stk.append(i)
        elif i not in first and check == False:
            stk.append(i)
    result = stk

else:
    pass

print(*result, sep="")

# 이제 후위표기식으로 변환
tmp = []
for k in result:
    try:
        if k == "(":
            pass
        elif 65 <= ord(k) <= 90:
            print(k, end="")
        elif k == ")":
            print(tmp.pop(), end="")
        else:
            tmp.append(k)
    except IndexError:
        pass
if len(tmp) != 0:
    print(*tmp)

 

코드의 문제점

중복괄호 input : (A+B)*C, output : (((A+B))*C)

괄호가 하나만 있어도 되는데 괄호가 있는채로 입력해온다면 괄호가 중복해서 들어간다...

 

 

괄호가 다 안닺힘 input : A+B*C*((D-E)*G) =>  (A+(((B*C)*(((D-E)*G)) 

보시면 왼괄호랑 우괄호 갯수가 맞지 않다...

 

이렇게 괄호 씌우는데부터 문제가 생겼고, 코드가 너무 길어져 나도 내 코드가 뭔지 모르게 되었다!

 

흑ㅠ

📎 문제 링크 : 후위 표기식

1918번: 후위 표기식