후위표기식 만들기(스택)

후위표기식 만들기(스택)

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

---

풀이

숫자일 때는 출력해주고, 연산자일 때는 조건문을 통해 연산을 해주거나 스택에 저장해주면서 우선순위를 두어야 한다.

 

숫자일 때 출력해주기 위해서 isdeciaml() 함수를 이용하는데,

isdecimal() 함수는 주어진 문자열이 int형으로 변환이 가능한지 알아내는 함수이다.
즉, str로 되어있는 문자열이나 리스트를 int형으로 변환 가능한지 판별하는 함수이다.

 

연산자일 때

( : 여는 괄호는 그 앞에 어떤 연산자가 있어도 그 뒤에 연산자부터 계산이 이루어지기 때문에, 어떠한 처리없이 스택에 추가해준다.

) : 닫는 괄호는 여는 괄호와 그 사이에 있는 모든 연산을 처리해주고, 마지막에 여는 괄호를 pop 해준다.

* / : 곱하기와 나누기는 그 전의 연산자(스택의 맨위)가 곱하기와 나누기일 때, 그 연산자를 처리해주고, 그 후에 곱하기와 나누기를 스택의 맨 위에 추가해준다. 

+ - : 더하기와 빼기는 그 전의 연산자(스택의 맨위)가 여는 괄호일 때만 바로 처리해주고, 그렇지 않으면 그냥 스택의 맨위에 추가해준다.

 

순위기 밀린 연산자들은 스택의 맨위에서 부터 하나씩 처리해준다.

---

코드

a = input()
stack = []
answer = ''

for x in a :
    # 피연산자일 경우
    if x.isdecimal():# 10진수인지 확인
        answer += x 
    
    # 연산자일 경우 +-*/()
    else:
        if x=='(':
            stack.append(x)         
        elif x== ')':
            while stack and stack[-1]!='(': # (를 만날 때까지 연산.
                answer += stack.pop()
            stack.pop() # 스택에 쌓여있는 ( 없에기

        elif x=='*' or x=='/': 
            # 스택이 비어있지 않고 스택의 마지막이 *나 /일 때
            while stack and (stack[-1]=='*'or stack[-1]=='/'):
                answer += stack.pop() # 끄집어내서 누적
            stack.append(x)
        elif x=='+' or x=='-': # +-는 항상 후순위
            while stack and stack[-1]!='(':
                answer += stack.pop() # (를 만날 때까지 연산.
            stack.append(x)
    
# 스택에 남아있는 것들 연산
while stack:
    answer += stack.pop()

print(answer)