✍ 문제
(문제 일부 생략)
중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오
✍ 입력
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 곱셈이 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다.
✍ 출력
첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오
✅ 코드
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
int main() {
string infix; //입력값: 중위 표기법
cin >> infix;
queue<char> operands; //피연산자 저장 큐 (FIFO 특징 사용)
stack<char> operations; //연산자 저장 스택 (LIFO 특징 사용)
vector<char> postfix; //후위 표기식 결과값 (동적배열 특징 사용)
operations.push('0'); //pop이나 top 연산 시 비어있는 스택으로 인한 컴파일 오류 방지
/*
* 피연산자와 연산자를 구분하여 각각 큐와 스택에 저장
*
* 연산자 우선순위 +, - < *, /
*
* 삽입되는 연산자가
* 1. 닫는 괄호 ')' 인 경우
* 2. operations 스택의 top의 우선순위가 현재 삽입되는 연산자의 우선순위와 같거나 높은 경우
*
* -> 현재 operands 큐에 저장되어있는 피연산자를 모두 postfix로 복사 (먼저 삽입된 것부터, FIFO)
* 1번 경우는 operations 스택에서 가장 가까운 여는 괄호 '(' 를 만날 때 까지
2번 경우는 operations 스택의 top의 우선순위가 현재 삽입되는 연산자의 우선순위보다 낮아지거나 top의 값이 '0'이 될 때 까지
현재 operations 스택에 저장되어 있는 연산자를 postfix로 복사 (나중에 삽입된 것부터, LIFO)
*
* 마지막에는 operands와 operations에 들어있는 모든 요소 다 털기!
*/
for (int i = 0; i < infix.length(); i++) {
if (infix[i] == '(') {
operations.push(infix[i]);
}
else if (infix[i] == ')') {
while (operands.size() != 0) {
postfix.push_back(operands.front()); //먼저 들어온 순서대로 pop
operands.pop();
}
while (operations.top() != '(') {
postfix.push_back(operations.top());
operations.pop();
}
operations.pop(); // '('도 삭제
} // 주석의 1번 경우
else if (infix[i] == '*' || infix[i] == '/') {
if (operations.top() == '*' || operations.top() == '/') {
while (operands.size() != 0) {
postfix.push_back(operands.front());
operands.pop();
}
while (operations.top() == '*' || operations.top() == '/') {
postfix.push_back(operations.top());
operations.pop();
}
} // 주석의 2번 경우
operations.push(infix[i]);
}
else if (infix[i] == '+' || infix[i] == '-') {
if (operations.top() == '(' || operations.top() == '0') { //top의 우선순위가 +, - 보다 낮은 경우
operations.push(infix[i]);
}
else {
while (operands.size() != 0) {
postfix.push_back(operands.front());
operands.pop();
}
while (operations.top() != '(' && operations.top() != '0') {
postfix.push_back(operations.top());
operations.pop();
}
operations.push(infix[i]);
} //주석의 2번 경우
}
else operands.push(infix[i]); //피연산자 저장
}
// 각 스택과 큐에 남은 것 다 postfix로 복사, 피연산자부터!
while (operands.size() != 0) {
postfix.push_back(operands.front());
operands.pop();
}
while (operations.top() != '0') {
postfix.push_back(operations.top());
operations.pop();
}
for (int i = 0; i < postfix.size(); i++) {
cout << postfix[i];
}
vector<char>().swap(postfix);
//cout << "size: " << postfix.size() << " capacity: " << postfix.capacity() << '\n';
//벡터의 메모리 해제 확인을 위한 코드
return 0;
}
✅ 코드풀이
스택 자료구조를 다뤘으니, 스택을 응용한 문제에 도전해봐야겠다 싶었는데 제일 먼저 생각나는게 후위 표기법이었다. 연산자와 피연산자의 위치에 따라 수식은 전위 표기법(prefix notation), 중위 표기법(infix notation), 후위 표기법(postfix notation) 3가지 종류로 표현할 수 있다.
백준 1918번은 이 중 중위 표기법을 후위 표기법으로 변환하는 문제였는데, 알고리즘을 생각해내는데 꽤 시간이 오래걸렸다. 처음에는 연산자와 피연산자를 구분하지 않고 하나의 스택에 담으며 해결하려고 하다보니 피연산자만 빼고 싶은데 중간에 연산자가 섞여 있다던가... 하는 문제가 발생했다.
이 문제의 핵심 포인트는 "연산자와 피연산자를 분리해서 자료구조에 담는 것"과 "언제 피연산자와 연산자를 비울 것인가" 이다.
✔️ 연산자와 피연산자
후위 표기법에서 피연산자의 순서는 입력값으로 들어온 중위 표기법의 피연산자의 순서와 동일하다.
예를 들어 (A+B)-C*D+E-F 라는 중위 표기법 수식이 있을 때, 후위 표기법을 사용한다고 해도 피연산자의 순서는 동일하게 ABCDEF 이다. (연산자는 피연산자 사이 어딘가에 들어가게 된다.)
따라서 피연산자의 경우, 먼저 들어온 것이 먼저 나와야 하는 FIFO 의 성질이 있기 때문에 피연산자를 담을 자료구조로 "큐"를 선택하였다.
반면 연산자는 우선순위나 닫는 괄호를 만남에 따라 나중에 들어온 것이 먼저 나와야 하는 LIFO 의 성질을 가지기 때문에 연산자를 담을 자료구조로는 "스택"을 선택하였다.
마지막으로 결과값을 저장하는 자료구조로는 동적배열인 "벡터"를 선택하였다. 벡터를 사용할 때는 꼭 메모리 해제 해주는 것까지! 신경써주자.
✔️ 중위 표기법 → 후위 표기법 알고리즘
연산자와 피연산자를 구분하여 각각의 자료구조에 넣어주었다면, 이제 각 연산자에 대해 우리가 취해야 할 행동들을 생각해봐야 한다. 피연산자는 어짜피 순서가 정해져 있으므로 신경쓰지 않아도 된다. 우리가 주목해야하는 건 연산자이다!
문제에서 주어진 연산자는 (, ), +, -, *, / 로 총 6가지이다.
기본적으로 중위를 후위로 바꾸는 방법은 연산자의 우선순위대로 계산을 하고, 계산을 할 때 연산자를 피연산자의 오른쪽으로 움직여주면 된다. 연산자의 우선순위는 괄호 → 곱셈* 나눗셈/ → 덧셈+ 뺄셈- 이다.
이제 중위 표기법을 후위 표기법으로 변환하기 위한 알고리즘을 정리해보자!
1. 연산자 stack은 top 연산자의 우선순위보다 높은 연산자만 push
우선순위대로 계산을 해야 하기 때문에 연산자 stack에는 top에 있는 것보다 우선순위가 높은 연산자만 stack 에 push 될 수 있다. 쉽게 말해 stack의 top에 +가 있는 경우는 *가 push 될 수 있다. 하지만 stack의 top에 /가 있는 경우 +는 push 될 수 없다! 글로 풀어놓자니 더 복잡한 것 같지만...ㅎ 한마디로 정리해서 연산자 stack에는 우선순위를 지켜야만 push 될 수 있다!
2. 넣어야 하는 연산자가 닫힌 괄호인 경우
→ 피연산자 queue에 담긴 요소들을 postfix 벡터로 복사
연산자 stack의 top이 가장 가까운 열린 괄호가 될 때까지 top 요소를 postfix에 복사한 후 pop
닫힌 괄호가 나왔다는 것은 괄호 안에 들어가 있는 수식을 계산할 때가 왔다는 것이다. 따라서 닫힌 괄호가 나올 때까지 피연산자 queue에 담겨졌던 모든 피연산자를 postfix로 옮겨준다. 그리고 가장 가까운 열린 괄호가 top이 될 때까지 연산자 stack의 top을 postfix로 옮긴 후 pop 해준다. 이 두 과정이 모두 끝났으면 피연산자 queue는 비어있고 stack의 top은 열린괄호일 것이다. 열린 괄호를 삭제 시켜주기 위해 while문이 끝난 뒤 한 번 더 stack pop을 해주면 끝난다.
3. 넣어야 하는 연산자가 현재 연산자 stack의 top 요소보다 우선순위가 낮은 경우
→ 피연산자 queue에 담긴 요소들을 postfix 벡터로 복사
연산자 stack의 top이 넣어야 하는 연산자의 우선순위보다 낮아질 때까지, 혹은 stack이 빌 때까지
top 요소를 postfix에 복사한 후 pop
괄호가 아닌 사칙연산자를 stack에 넣어야 하는 경우, 현재 stack의 top에 있는 연산자와 우선순위를 비교해야 한다. 만약 넣어야 하는 연산자가 stack의 top보다 우선순위가 낮거나 같다면, 피연산자 queue에 담겨졌던 모든 피연산자를 postfix로 옮긴 후 stack의 top보다 우선순위가 높아질 때까지 top 연산자를 postfix로 옮기고 pop 해야한다.
이 과정에서 stack과 queue에 담긴 요소를 postfix로 옮긴다는 것은 우선순위에 따라 계산을 수행해주는 것이라고 생각하면 된다. 글을 조리있게 정리를 못해서 너무 어렵게 풀이한 것 같은데😭 나중에 더 논리적으로 정리 해보겠다...ㅠㅠ
어쩃든 해당 문제에서는 중위 표기법을 후위 표기법으로 변환하는 과정을 논리적으로 정리하고, 저장해야 하는 데이터의 사용 방법에 따라 적절한 자료구조를 사용하는 것이 중요한 문제였다. 앞으로 스택을 이용하여 풀 수 있는 문제들을 더 다뤄보면서 다양한 경우에 적절한 자료구조를 생각해내는 연습을 해보고자 한다. 빠잇팅 💪💪
