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

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

1918번: 후위 표기식

문제

수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.

이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.

예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 (a+bc*)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.

다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.

결과: ABC*+DE/-

이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

입력

첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다. 

---

중위표기식을 후위표기식으로 변환하는 과정을 보면 괄호를 출력하지 않고 연산자를 뒤로 빼는 규칙을 확인할 수 있다.

이 말인 즉슨 비연산자가 나오면 바로 출력을 하고 연산자는 뒤로 보내야 하기 때문에 저장했다가 이후에 출력을 하는 것이다.

또한, 괄호가 추가된 식에서 괄호 블럭의 경우 늦게 나온 연산자가 괄호 블록 뒤에 먼저 출력되는 것을 확인할 수 있으며 이는 스택을 연상시킨다.

'('가 들어올 경우 스택에 push 한다.

')'가 들어올 경우 (를 만날 때까지 push 한다. 한 연산 블록이기 때문이다. 

'*' 혹은 '/' 가 들어온 경우 먼저 스택에 존재하던 '*'와 '/'를 출력한 뒤 pop 한다. 같은 우선순위를 가지면 왼쪽에 있던 식이 계산되어야 하기 때문이다. 그다음 자기 자신을 스택에 push 한다.

'+' 혹은 '-'의 경우 우선순위가 낮기 때문에 '('가 나올 때까지 모든 연산자를 출력한다. 그다음 자기 자신을 스택에 push 한다.

 

---

 문제를 보고 스택을 활용해야겠다는 생각과 알파벳은 바로 출력을 해야한다는 것까지는 생각을 하였지만 연산자의 출력 순서를 쉽게 생각해 내지 못했다. 한 블로그를 참고한 결과 자신과 우선순위가 같거나 높으면 출력한 다음 push 한다는 글을 읽고 조금 더 생각을 해보았고 구현을 할 수 있었다. 전위,중위,후위 는 정말 유명한 유형의 문제들인데 이렇게 바로바로 풀지 못하니 아직 갈길이 먼 것 같다!

 친구들과 스프링 스터디를 하다 solved.ac에 클래스라는 것을 알게 되었다. 기존에는 골드3~5 레벨의 문제들을 임의로 선택하여 풀었는데 최근에 BFS 문제들만 푸는 것 같던 찰나 여러 레벨의 문제가 모여있는 클래스를 알게되었다. 클래스 4,5의 경우 상당 부분의 문제를 이미 풀었던 것이다. 그래도 남은 문제들이 있고 문제 편식을 막으면서 재미있게 풀 수 있을 것 같아 기대된다!