[Baekjoon] 1918번: 후위 표기식

🥅 문제

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

 

🔍 설계

후위 표기식을 나타내는 데는 스택을 사용한다. A+B-C의 경우, ABC-+ 인데, 출력 순서를 고려하면, 먼저 들어온 +가 나중에 출력되어야 하기 때문이다.

 

알파벳이면, 그냥 출력하여 스택에는 괄호와 연산자만 담기게 한다.

 

괄호 내부의 식을 고려하기 위해, 현재 문자가 '('이면 스택에 그냥 추가하고, ')'이면, 괄호 내부에서 아직 출력하지 않은 연산자를 출력하고, '('를 제거하여 괄호 내부의 식을 끝낸다.

 

현재 문자가 괄호가 아닌 연산자이면, 뒤에 괄호가 올 수 있으므로, 마지막에 스택에 추가해야 한다. 괄호에 대한 연산자를 먼저 출력하고, 그 이후에 출력해야 하기 때문이다.

 

마지막에 스택에 추가하기 전에 연산자가 '*' 또는 '/'이면,  식 내부에서 우선순위가 가장 높으므로,  '*' 또는 '/'를 모두 출력한다. 그리고 스택에 추가한다.

 

마지막에 스택에 추가하기 전에 연산자가 '+' 또는 '-'이면,  식 내부에서 우선순위가 가장 낮으므로, 스택에 있는 모든 연산자를 출력한다. 그리고 스택에 추가한다.

 

👊 풀이

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

string eq;
stack<char> s;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> eq;
	for (int i = 0; i < eq.length(); i++) {
		if (eq[i] >= 'A' && eq[i] <= 'Z') {
			cout << eq[i];
		}
		else if (eq[i] == '(') {
			s.push(eq[i]);
		}
		else if (eq[i] == ')') {
			while (!s.empty() && s.top() != '(') {
				cout << s.top();
				s.pop();
			}
			s.pop();
		}
		else if (eq[i] == '*' || eq[i] == '/') {
			while (!s.empty() && (s.top() == '*' || s.top() == '/')) {
				cout << s.top();
				s.pop();
			}
			s.push(eq[i]);
		}
		else if (eq[i] == '+' || eq[i] == '-') {
			while (!s.empty() && (s.top() != '(')) {
				cout << s.top();
				s.pop();
			}
			s.push(eq[i]);
		}
	}
	while (!s.empty()) {
		cout << s.top();
		s.pop();
	}
	
	return 0;
}