알고리즘/Baekjoon
[PS] 후위 표기식 / C++ (백준 1918번)
dh_0e
2025. 4. 20. 16:04
stack, vector를 사용해서 문제를 적절히 구현하면 되는 자료구조 문제
(((A+B)))같은 식은 안 나올 줄 알고 처리를 안 해놨다가 런타임 에러 받자마자 직감하고 처리해 줬다.
- 중위 표기식에 괄호 씌우기
- *, / 먼저 찾아서 수식의 위치를 make_pen 함수에 매개변수로 보낸다.
- +, - 도 찾아서 똑같이 make_pen 함수를 돌려준다.
- make_pen()은 찾은 수식의 위치를 매개변수로 받아 좌, 우로 식을 찾는다. 식은 알파벳 하나 또는 괄호로 이루어진 식으로 좌, 우의 식에 양 옆에 괄호가 이미 있다면 return, 한쪽이라도 괄호가 없다면 괄호를 삽입한다.
- 수식과 대응되는 괄호 찾아 후위 표기식으로 만들기
- '('는 st_op 스택에 위치를 저장
- 알파벳은 pass
- 수식은 st_cal에 마찬가지로 위치 저장
- ')'가 나오면 st_cal.top()에 저장된 수식의 위치가 괄호 안에 있는지 확인 ( '(A+B+(C))'같은 식도 나올 수 있음 )
- 괄호 안에 수식이 없는 ')' 삭제, '(' 삭제 (꼭 뒤에서부터 순서로 해야 함. >> erase 하면 위치가 바뀌기 때문)
- st_op.pop()
- 수식이 있다면 ')' 위치에 수식 삽입, 수식 삭제, '(' 삭제 (꼭 뒤에서부터 순서로 해야함. >> erase하면 위치가 바뀌기 때문)
- st_op.pop()
- st_cal.pop()
- i값 조정
- 괄호 안에 수식이 없는 ')' 삭제, '(' 삭제 (꼭 뒤에서부터 순서로 해야 함. >> erase 하면 위치가 바뀌기 때문)
#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
#include<cstring>
using namespace std;
char input[101];
vector<char> vec;
int make_pen(int mid) {
int left, right, l_op = 0, r_op = 0;
for (left = mid; left >= 0; left--) {
if (vec[left] >= 'A' && vec[left] <= 'Z') {
if (l_op == 0)break;
}
else if (vec[left] == ')')l_op--;
else if (vec[left] == '(') {
l_op++;
if (l_op == 0)break;
}
}
for (right = mid; right < vec.size(); right++) {
if (vec[right] >= 'A' && vec[right] <= 'Z') {
if (r_op == 0)break;
}
else if (vec[right] == '(')r_op--;
else if (vec[right] == ')') {
r_op++;
if (r_op == 0)break;
}
}
if ((left != 0 && vec[left - 1] == '(') && (right != vec.size() - 1 && vec[right + 1] == ')')) {
return 0;
}
else {
vec.insert(vec.begin() + right + 1, ')');
vec.insert(vec.begin() + left, '(');
return 1;
}
}
int main()
{
scanf("%s", input);
for (int i = 0; i < strlen(input); i++) {
vec.push_back(input[i]);
}
for (int i = 0; i < vec.size(); i++) {
if (vec[i] == '*' || vec[i] == '/') {
make_pen(i);
}
}
for (int i = 0; i < vec.size(); i++) {
if (vec[i] == '+' || vec[i] == '-') {
make_pen(i);
}
}
int i = 0;
stack<int> st_op, st_cal;
while (1) {
if (i == vec.size())break;
if (vec[i] == '(') {
st_op.push(i);
i++;
continue;
}
else if (vec[i] == ')') {
if (st_cal.size() == 0 || st_cal.top() < st_op.top()) {
vec.erase(vec.begin() + i);
vec.erase(vec.begin() + st_op.top());
st_op.pop();
i--;
continue;
}
vec[i] = vec[st_cal.top()];
vec.erase(vec.begin() + st_cal.top());
vec.erase(vec.begin() + st_op.top());
}
else if (vec[i] < 'A') {
st_cal.push(i);
i++;
continue;
}
else {
i++;
continue;
}
i -= 2;
st_cal.pop();
st_op.pop();
i++;
}
for (int i = 0; i < vec.size(); i++)printf("%c", vec[i]);
return 0;
}