문제
풀이
- 스택을 이용한다.
- 피연산자는 바로 answer의 뒤에 추가한다.
- 연산자는 다음으로 처리된다.
- 스택이 비어있다면 스택에 연산자를 push한다.
- 연산자는 스택의 top과 우선순위를 비교하여 자신보다 우선순위가 낮을 때까지 top을 answer의 뒤에 추가하고 스택을 pop한다. 그 후, 스택에 자신을 push한다.
- ' ( '는 바로 스택에 push한다.
- ' ) '는 스택에서 ' ( '가 나올때까지 top을 answer의 뒤에 추가하고 스택을 pop한다. 그 후, ' ( '를 스택에서 삭제한다.
코드
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <unordered_map>
using namespace std;
// 연산자 우선순위
unordered_map<char, int> priority = {
{'(', 0},
{'-', 1},
{'+', 1},
{'*', 2},
{'/', 2}
};
int main()
{
string s;
stack<char> st;
string answer;
cin >> s;
for (int i = 0; i < s.size(); ++i)
{
if (65 <= int(s[i]) && int(s[i]) <= 90)
{
answer.push_back(s[i]);
}
else if (s[i] == '(')
{
st.push(s[i]);
}
else if (s[i] == ')')
{
// '('가 top일 때까지 top을 answer의 끝에 추가하고 pop
while (st.top() != '(')
{
answer.push_back(st.top());
st.pop();
}
// '('를 pop
st.pop();
}
else
{
// 스택의 top이 s[i]보다 낮을 때까지 top을 answer의 끝에 추가하고 pop
while (!st.empty() && priority.find(s[i])->second <= priority.find(st.top())->second)
{
answer.push_back(st.top());
st.pop();
}
st.push(s[i]);
}
}
// 스택에 남은 연산자를 answer의 끝에 추가
while (!st.empty())
{
answer.push_back(st.top());
st.pop();
}
cout << answer;
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준][C++] 17070: 파이프 옮기기1 (0) | 2023.09.22 |
---|---|
[백준][C++] 11444: 피보나치 수 6 (0) | 2023.09.21 |
[백준][C++] 1238: 파티 (0) | 2023.09.19 |
[백준][C++] 21736: 헌내기는 친구가 필요해 (1) | 2023.09.18 |
[백준][C++] 20529: 가장 가까운 세 사람의 심리적 거리 (0) | 2023.09.17 |