[백준 C++] 1918 후위 표기식 - 스택

1918번: 후위 표기식

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	string Origin;
	cin >> Origin;

	stack<char> Operator;
	for (int i = 0; i < Origin.size(); ++i)
	{
		char Ch = Origin[i];
		if (Ch >= 'A')
		{
			cout << Ch;
			continue;
		}

		switch (Ch)
		{
		case '(':
			Operator.push(Ch);
			break;

		case ')':
			while (Operator.top() != '(')
			{
				cout << Operator.top();
				Operator.pop();
			}
			Operator.pop();
			break;

		case '*':
		case '/':
			if (!Operator.empty()
				&& (Operator.top() == '*' || Operator.top() == '/'))
			{
				cout << Operator.top();
				Operator.pop();
			}
			Operator.push(Ch);
			break;

		case '+':
		case '-':
			while (!Operator.empty()
				&& Operator.top() != '(')
			{
				cout << Operator.top();
				Operator.pop();
			}
			Operator.push(Ch);
			break;
		}
	}

	while (!Operator.empty())
	{
		cout << Operator.top();
		Operator.pop();
	}
}

---

 

스택 자료구조를 이용해서 푸는 문제입니다.

입력된 문자열에서 한 문자씩 방문해서 각 문자에 따라 출력 또는 스택에 넣거나 빼거나 해줍니다.

 

1. 알파벳: 바로 출력

2. +, -: 스택에 저장된 연산자들을 '('를 만나기 전까지 모두 출력, 삭제 후 스택에 저장

3. *, /: 스택에 저장된 top 연산자가 '*' 또는 '/'라면 해당 연산자 출력, 삭제 후 스택에 저장

4. (: 스택에 저장

5. ): 스택에 저장된 연산자들을 '('를 만나기 전까지 모두 출력, 삭제 후 남은 '('까지 삭제

 

문자열 탐색이 종료되면 스택에 저장된 모든 연산자를 출력, 삭제해줍니다.