[python] 1918. 후위 표기식

 

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

 

 

풀이

 

오늘은 stack, queue, deque의 문제 유형인 후위 표기식을 풀어보겠습니다.

 

연산자 우선순위

1. () 

2. * /

3. + -

 

stack을 이용하여 연산자의 우선순위를 고려하여 문제를 해결해보도록 하겠습니다. 

 

리스트에 식전체를 넣어 for문을 통해 한 문자씩 확인합니다.

1. ()를 확인

2. * / 인지를 확인하고, 먼저 들어온 같은 우선순위에 있는 * /는 모두 출력 문자열에 추가

3. 현재 연산자를 stack에 추가

4. + - 인지를 확인하고, + - 보다 낮은 우선순위의 연산자가 없기 때문에 자신보다 우선순위가 높은 연산자들을 모두 출력 문자열에 추가

5. )를 발견하면 ( 와 ) 사이에 있는 모든 연산자들을 출력 문자열에 추가하고 (를 pop 

6. 마지막으로 남아있는 stack을 pop하여 출력 문자열에 추가해주면 끝 - 

 

 

postfix = list(input())

# 알파벳이 들어오면 결과값 문자열에 추가하고
# 연산자가 들어오면 우선순위에 맞게 처리해준다.

stack = []
ans = ""
for s in postfix:
    if s.isalpha(): # 알파벳인지 확인
       ans += s
    else: # 연산자일 때
        if s == '(':
            stack.append(s)
        elif s == '*' or s == '/':
            # */인지를 확인하고 먼저 들어온 같은 우선순위에 있는 */는 모두 결과 문자열에 추가
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                ans += stack.pop()
            stack.append(s)
        elif s == '+' or s =='-':
            # +-는 해당 연산자보다 우선순위가 낮은 연산자가 없으므로, 자신보다 우선순위가 높은 것들은 모두 결과 문자열에 추가
            while stack and stack[-1] != '(':
                ans += stack.pop()
            stack.append(s)
        elif s == ')':
            while stack and stack[-1] != '(':
                ans += stack.pop()
            stack.pop() # ( 나오면 pop

while stack:
    ans += stack.pop()

print(ans)