★ solved.ac 난이도 : G3
(2021년 12월 29일 기준)
[문제 링크]
1918번: 후위 표기식
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의
www.acmicpc.net
[문제 분석]
스택을 활용한 수식 변환 문제
[풀이]
이 문제는, (사람이 주로 사용하는) 중위 수식을 후위 수식으로 바꾸는 문제입니다.
이 문제도 자료구조를 예습하면서 접하게 된 문제인데요,
여기에서도 LIFO(후입선출)의 스택을 사용했습니다.
후위 수식은, 컴파일러가 주로 사용하는 수식 형태로,
연산자가 피연산자의 뒤에 나오는 수식입니다.
또한, 괄호 없이 우선순위를 반영할 수 있습니다.
문제 본문에도 살짝 나와있지만, 이제부터 중위 수식을 후위 수식으로 바꿔보겠습니다.
먼저, 중위 수식을 좌에서 우로 스캔하게 됩니다.
여기에서 피연산자를 만나게 되면, 바로 후위 수식으로 출력합니다.
(중위 수식과 후위 수식의 피연산자들의 순서는 같습니다.)
단, 연산자를 만나게 된다면, 출력을 보류하고, 어딘가에 저장합니다.
문제는, 어딘가에 저장된 연산자들의 출력 순서입니다.
(여기에서 약간 어려워집니다. 주의하세요!!)
먼저 연산자들의 출력 순서를 요약하자면,
1. 연산자의 스캔 순서대로 우선 순위가 높아지는 경우
이 경우에는, 나중에 스캔된 연산자 순서대로 출력하시면 됩니다.
예시) A+B*C => ABC*+
2. 스택에 존재하는 연산자의 우선 순위가 현재 처리 중인 연산자보다 높거나 같은 경우
여기에서 조금씩 어려워지는데요, 스택 상단의 연산자를 먼저 출력 후, 처리 중인 연산자를 스택에 삽입하시면 됩니다.
예시) A*B+C => AB*C+
예시) A+B-C => AB+C-
3. 수식에 괄호가 포함된 경우
이 부분이 가장 어려운 부분입니다.
먼저, 여는 괄호를 먼저 스택에 삽입합니다. 그리고 이를 우선순위가 가장 낮은 연산자로 취급합니다.
(여기에서도 위에서 언급한 2가지 경우를 지켜야 합니다.)
처리 도중, 닫는 괄호를 만나게 되면, 여는 괄호가 삭제될 때 까지 (여는) 괄호 위에 쌓인 모든 연산자들을 출력합니다.
예시) (A+B)*C => AB+C*
예시) A*(B+C/D) => ABCD/+*
(자세한 내용은 아래의 소스를 참고해주세요~!)
[참고 자료]
천인국 교수님 외 2인, 「C언어로 쉽게 풀어 쓴 자료구조」 : 개정판, 생능출판, 200-07쪽
[소스 코드]
만약 틀린 부분이 있다면 지적 부탁드릴게요~! (댓글 환영!!)