[BOJ 1918, 조금 어려움] 후위 표기식 (C++)

유명한 문제지만 나처럼 푼 사람은 아무도 없는 것 같아서 내 풀이를 가져왔다

 

개인적 난이도 : 조금 어려움

---

 

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

1918번: 후위 표기식

 

예전에 못 풀고 고생하던 흔적이 있다

 

1. 알파벳을 넣어줄 queue를 사용한다
2. 연산자를 넣어줄 stack을 사용한다. 연산자와 그 연산자의 우선순위를 pair로 집어넣는다.
3. 연산자의 우선순위 비교를 편하게 하기 위해, map을 사용했다.
   1. + 와 - 의 우선순위는 0으로 놓는다
   2. * 와 / 의 우선순위는 1으로 놓는다
   3. ( 여는 괄호가 등장한 이후의 모든 연산자들엔 +2의 우선순위 보너스를 준다
   4. ) 닫는 괄호가 등장한 이후의 모든 연산자들엔 -2의 우선순위 보너스를 준다
4. 식의 처음부터 끝까지 스위핑하면서,
   
   1. 알파벳이 나오면 queue에 집어넣는다
   2. 연산자가 나오면 앞 연산자와 비교하며 stack에 집어넣는다
      1. 앞 연산자 우선순위와 같거나 우선순위가 더 작다면, queue에 있는 알파벳을 모조리 꺼내며 출력하고 stack이 완전히 비거나 stack top보다 내 우선순위가 커질 때까지 stack을 비우며 출력한다
      2. 앞 연산자 우선순위보다 내 우선순위가 더 크다면, 스택에 집어넣는다
5. queue에 있는 나머지 알파벳들을 출력하고, stack에 남아있는 나머지 연산자들을 출력한다

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int,int>
using namespace std;

int main(){
	fastio;
	string s;cin>>s;
	map<char,int> lev;
	lev.insert({'+',0});
	lev.insert({'-',0});
	lev.insert({'*',1});
	lev.insert({'/',1});
	int br=0;//괄호에 의한 우선순위 보너스
	queue<char> qq;
	stack<pair<char,int>> ss;

	for (auto i:s)
	{
		if(isalpha(i)){qq.push(i);continue;}
		if(i=='('){
			br+=2;
			continue;
		}
		if(i==')'){
			br-=2;
			continue;			
		}
		if(!ss.empty()&&ss.top().second>=lev[i]+br){
			while (!qq.empty())
			{
				cout<<qq.front();
				qq.pop();
			}
			while (!ss.empty()&&ss.top().second>=lev[i]+br)
			{
				cout<<ss.top().first;
				ss.pop();
			}
			ss.push({i,lev[i]+br});
			continue;			
		}
		else{
			ss.push({i,lev[i]+br});
		}
	}
	while (!qq.empty())
	{
		cout<<qq.front();
		qq.pop();
	}
	while (!ss.empty())
	{
		cout<<ss.top().first;
		ss.pop();
	}
	return 0;
}