3. 후위 표기식 만들기

후위표기식 만들기

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

 

 

1. 문제풀이 

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)

 

2. 해설 

 

1.  elif x=='*' or x=='/':
            while stack and (stack[-1]=='*' or stack[-1]=='/'):

   

   →동일순위 연산자임에도 스택에 동일순위 연산자가 먼저 들어가서 우선순위가 높은 경우 

 

 

 

2. elif x=='+' or x=='-':
            while stack and stack[-1]!='(':

 

   → "+" 나 " - " 이전에 스택에  

       동순위연산자 "+" 또는 " - " ,  우선순위 연산자 " * " 또는 " / "가 먼저 있는 경우
      " ( " 여는 괄호를 만나기 전까지 계속 pop한다. 

 

3.  elif x==')':
            while stack and stack[-1]!='(':
                res+=stack.pop()
            stack.pop()     ←--------------------" ( " 여는 괄호까지 pop한다.

      

 

4. while stack:                  스택에 남아있는 연산자가 있는 경우 
       res+=stack.pop()      연산자를 전부 pop한다.

 

 

3. 보충해설

 ▶ + 와   - 가 동일한 우선순위를 갖는다고 할지라도 스택에 들어 있는 + 또는 - 를 먼저 pop 한다.

     *  와   /  가 동일한 우선순위를 갖는다고 할지라도 스택에 들어 있는 * 또는 - 를 먼저 pop 한다.

 

▶ 여는 괄호 " ( "는 무조건 stack에 append 한다.

 

▶ 여는 괄호 " (  "를 넣은 다음에 + 또는 * 가 스택에 들어가고, 그 다음에  " - "가 오는 경우에는 

     + 와  * 가  " - "  보다 우선 순위가 높으므로    "( " 여는 괄호 전까지   + 와  *  를 모두   pop시킨다.