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

다이어트 중이라 배고파서 집중이 제대로 안 됐다... 그래서 언제 스택에 있는 값을 모두 pop하고, 언제 그냥 스택에 push하는지 등을 구분 못 했음

• 연산자의 경우
  • top보다 우선순위가 크면 stack에 push
  • top보다 우선순위가 작거나 같으면
    top의 우선순위를 이길 때까지 stack을 pop
• (을 만나면, stack에 그냥 push
• )을 만나면, (을 만날 때까지 stack을 pop
• 피연산자는 그냥 push

코드가 더럽긴 하다...

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;

int main()
{
	vector<char> printSentence;
	stack<char> operators;

	unordered_map<char, int> priority;
	priority['*'] = 2;
	priority['/'] = 2;
	priority['+'] = 1;
	priority['-'] = 1;

	string line;
	cin >> line;

	for (int i = 0; i < line.size(); i++)
	{
		if (line[i] > 64) printSentence.push_back(line[i]);
		else
		{
			if (line[i] == '(')
			{
				operators.push('.');
			}
			else if (line[i] == ')')
			{
				while (true)
				{
					if (operators.top() == '.')
					{
						operators.pop();
						break;
					}
					printSentence.push_back(operators.top());
					operators.pop();
				}
			}
			else if (!operators.empty() && priority[line[i]] > priority[operators.top()])
			{
				operators.push(line[i]);
			}
			else
			{
				while (!operators.empty())
				{
					if (priority[operators.top()] < priority[line[i]]) break;
					if (operators.top() == '.') break;
					printSentence.push_back(operators.top());
					operators.pop();
				}
				operators.push(line[i]);
			}
		}
	}

	while (!operators.empty())
	{
		if(operators.top() != '.') printSentence.push_back(operators.top());
		operators.pop();
	}

	for (int i = 0; i < printSentence.size(); i++)
	{
		cout << printSentence[i];
	}
}