[백준 1918번] 후위 표기식 - python

문제 링크

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

풀이 - 다른 블로그 참고 

- 처음엔 트리 문제인 줄 알았는데 stack을 사용하는 문제

입력으로 들어온 문자열의 문자들에 대하여

1. 문자가 알파벳이면 ans에 추가

 

2. 문자가 연산자라면

연산자의 우선순위가 

1. '(', ')'

2. '*', '/'

3. '+', '-' 이므로

 

1) '(' 일 때 stack에 추가

2) ')'일 때 stack에 문자가 있고, stack의 마지막 문자가 '('이 아닐 때까지 스택에 있는 연산자들 pop하여 ans에 추가

'(' 제거를 위해 한 번 더 pop

3) '*', '/' 일 때 

같은 연산자 우선순위인 '*'나 '/'가 나올 때까지 스택에 있는 연산자들 pop하여 ans에 추가 

현재 연산자 스택에 추가 

4) '+', '-' 일 때 

가장 낮은 우선순위이므로 자신보다 우선순위 높은 것들 모두 pop하여 ans에 추가 

 

3. 스택에 남은 연산자들 ans 에 추가 

4. 출력 

s = list(input())
stack = []
ans = ""
for i in s:
    if i.isalpha():
        ans += i 
    else :
        if i == '(':
            stack.append(i)
        elif i == ')':
            while stack and stack[-1] != '(':
                ans += stack.pop()
            stack.pop()
        elif i == '*' or i =='/':
            while stack and (stack[-1] =='*' or stack[-1] =='/' ):
                ans += stack.pop()
            stack.append(i)
        elif i == '+' or i == '-':
            while stack and stack[-1] != '(':
                ans += stack.pop()
            stack.append(i)
            
while stack:
    ans += stack.pop()
print(ans)