[스택 & 큐] - 후위 표기식

후위 표기식

중위표기식이 입력되면 후위표기식으로 변환하는 프로그램을 작성하세요.
중위표기식은 우리가 흔히 쓰은 표현식입니다.

즉 3+5 와 같이 연산자가 피연산자 사이에 있 으면 중위표기식입니다.
후위표기식은 35+ 와 같이 연산자가 피연산자 뒤에 있는 표기식입니다.
예를 들어 중위표기식이 3+5*2 를 후위표기식으로 표현하면 352*+ 로 표현됩니다.
만약 다음과 같이 연산 최우선인 괄호가 표현된 식이라면
(3+5)*2 이면 35+2* 로 바꾸어야 합니다.

※후위 표기식이 이해가 안되면 구글링으로 공부해보는 것도 좋습니다.

 

▣ 입력설명
첫 줄에 중위표기식이 주어진다. 길이는 100을 넘지 않는다. 식은 1~9의 숫자와 +, -, *, /, (, ) 연산자로만 이루어진다.

▣ 출력설명 후위표기식을 출력한다.

 

▣ 입력예제 1

3+5*2/(7-2)

▣ 출력예제 1

352*72-/+

 

▣ 입력예제 2

3*(5+2)-9

▣ 출력예제 2

352+*9-

 

나의 코드

arr=input()
res=[]
stack=[]

for x in arr:
    if x.isdecimal():
        res.append(x)
    elif x == '+' or x == '-':
        if stack and stack[-1]!='(':   
            res.append(stack.pop())
        stack.append(x)
    elif x == '*' or x =='/':
        if stack :
            if stack[-1]=='*' or stack[-1]=='/':
                res.append(stack.pop())
        stack.append(x)
    elif x=='(':
        stack.append(x)
    elif x==')':
        while True:
            if stack[-1] =='(':
                stack.pop()
                break
            else:
                res.append(stack.pop())

while stack:
    res.append(stack.pop())

answer=''.join(map(str,res))
print(answer)

꼼꼼히 고민해서 코드를 잘 짠것같다.

우선 입력 값을 받은 후 해당 값이

1. 숫자이면 바로 res에 넣었다.

2. +,-이면 stack이 있으면서  stack의 가장 윗 값이 '(' 가 아니면 바로 그 윗값을 res에 넣었다 

 (+,-는 모든 우선 순위가 가장 끝이므로 스택에 있는 부호를 무조건 pop )

( '(' 조건 체크는 모든 코드를 거의 작성한 후 디버깅 하며 발견)

3. *,/ 인 경우 스택의 바로 뒤의 값이 /,*인 경우( 같은 우선순위이지만 먼저나온값은 먼저 계산해야함)

4. ( 인 경우 )를 만날 때 까지 괄호 사이 값들을 저장하는 포인터 역활을 위해 바로 stack에 넣는다.

5. ) 인 경우 (를 만날 때까지 스택의 값들을 pop

6. 마지막으로 스택이 빌때 까지 반복문을 돌며 스택에 있는 값들을 순서대로 pop 하여 res에 넣는다.

 

 

정답 코드

import sys
sys.stdin=open("input.txt", "r")
a=input()
stack=[]
res=''
for x in a:
    if x.isdecimal():
        res+=x
    else:
        if x=='(':
            stack.append(x)
        elif x=='*' or x=='/':
            while stack and (stack[-1]=='*' or stack[-1]=='/'):
                res+=stack.pop()
            stack.append(x)
        elif x=='+' or x=='-':
            while stack and stack[-1]!='(':
                res+=stack.pop()
            stack.append(x)
        elif x==')':
            while stack and stack[-1]!='(':
                res+=stack.pop()
            stack.pop()
while stack:
    res+=stack.pop()
print(res)

나의 코드와 동일하다 !