✓

태그:

CLASS 4 ESSENTIAL

연산자와 피연산자를 구분해서 쌓아야겠습니다…!!

풀이 비스무리한거 보기

중위 표기식으로 표현된 사칙연산을 후위 표기식으로 바꾸는 문제입니다. 이 문제는 고려해야 할 점이 여러 개 있는데, 이는 아래와 같습니다.

• 연산의 우선순위
• 괄호의 처리
• 같은 우선순위의 연산의 경우 왼쪽부터 처리하기

이를 모두 만족시키기 위하여 스택을 사용합니다. 연산자와 피연산자를 따로 저장하는데, 피연산자는 그냥 피연산자 스택에 push, 연산자를 넣을 때는 연산자에 따라 취하는 행동이 다릅니다. 그 내용은 아래와 같습니다.

• 사칙연산 연산자(+, -, *, /): 연산자 스택의 top이 자신보다 우선순위가 높거나 같은 사칙연산 연산자이면 연산 실행 후 연산자 스택에 push
• (: 연산자 스택에 push
• ): 연산자 스택의 top이 (가 될 때까지 연산 실행, (가 나오면 연산자 스택을 pop

여기서 연산 실행¹이란, 피연산자 스택의 가장 위의 두 원소와 연산자 스택의 가장 위 원소를 후위 표기식으로 표기하는 것입니다. 예를 들어, 피연산자: A BC* 연산자: + 일 때 연산 실행을 하면 피연산자의 A와 BC*, 그리고 연산자의 +를 pop한 후, 그대로 이어붙인 ABC*+를 피연산자 스택에 다시 push합니다. 이를 반복하면 알맞은 후위 표기식을 얻을 수 있습니다.

---

1. 임의로 붙인 이름입니다. 제 코드에서 6줄짜리 내용이 완전히 같은 부분이 여러 번 나오는데, 이를 편의 상 연산 실행이라고 지칭했습니다. ↩

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-01-27 23:10:57

---