[백준] 1918 후위 표기식

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

변환된 정답을 저장하는 스택과 연산자와 괄호를 저장하는 스택을 생성하여 관리하였습니다.

알파벳은 바로 정답 스택에 쌓았고, 괄호와 연산자의 우선순위에 따라 정답에 추가하였습니다.

2) 알고리즘

• 자료구조

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

infix = sys.stdin.readline().rstrip()                       # 중위 표현법

answer = []                                                 # 후위 표현법으로 변형된 정답
op = []                                                     # 괄호 및 연산자가 들어갈 스택

for c in infix:                                             # 앞에서부터 반복
    if c.isalpha():                                         # 알파벳이라면 바로 정답에 넣기
        answer.append(c)
    elif c == '(':                                          # 여는 괄호가 나타나면 연산자 스택에 쌓기
        op.append(c)
    elif c == ')':                                          # 닫는 괄호가 나오면 여는 괄호가 나오기 전까지의 연산들 모두 진행 필요
        while op and op[-1] != '(':                         
            answer.append(op.pop())
        op.pop()                                            # 여는 괄호는 제거
    elif c == '+' or c == '-':                              # +나 - 는 우선순위가 제일 낮으므로 앞에 있던 연산자들 모두 연산 처리
        while op and op[-1] != '(':
            answer.append(op.pop())
        op.append(c)                                        # 현재 나온 연산자는 연산자 스택에 추가
    elif c == '*' or c == '/':                                                  # *나 / 연산자는 우선순위가 상대적으로 높으므로
        while op and op[-1] != '(' and (op[-1] != '+' and op[-1] != '-'):       # 이전에 쌓인 연산자가 +나 - 가 아니면 연산 처리
            answer.append(op.pop())
        op.append(c)

answer.extend(op[::-1])             # 남아 있는 연산자들 모두 추가

print(''.join(answer))

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

문제에서 제시한것처럼 중위표현식에서 괄호를 모두 붙여주었으나, 괄호를 모두 붙여주는 방식에 어려움을 느꼈습니다.

이후 괄호를 추가하지 않아도 바로 후위 표기식으로 변환해도 괜찮다는 사실을 인지하고 바로 변환하였습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

1918번: 후위 표기식

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다