백준 1918 후위 표기식

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

1918번: 후위 표기식

 

후위 표기식을 하는 것

 

주의할 점은 우선순위가 낮은 연산자일수록 Stack에 오래 남아있어야 한다. 그래야 나ㅏㅏㅏ중에 나오게 된다.

 

코드를 보면 무슨 말인지 확 이해될 것이다.

 

*나 /가 등장하면 stack에서 *나 / 이외의 연산자를 만날 때까지 pop을 하고 결과 문자열에 더해준다.

그 결과 '(' 와 '+' '-'는 stack에서 pop 되지 않는다.

 

 

/* 후위 표기식 */

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	string s,res; cin >> s;
	
	stack<char> st;

	for (int i = 0; i < s.size(); i++) {
		
		if (s[i] >= 'A' && s[i] <= 'Z') {
			res += s[i];
		}
		else { // 스택 밑에 깔릴 수록 나중에연산되는 애임
			switch (s[i]) {
			case '*': 
			case '/': 
				while (!st.empty() && (st.top() == '*' || st.top() == '/')) {
					res += st.top();
					st.pop();
				}
				st.push(s[i]);
				break;

			case '+':
			case '-':
				while (!st.empty() && !(st.top() == '(')) {
					res += st.top();
					st.pop();
				}
				st.push(s[i]);
				break;
			case ')':
				while (!(st.top() == '(')) {
					res += st.top();
					st.pop();
				}
				st.pop();
				break;

			case '(':
				st.push('(');
				break;
			}
		}
	}

	while (!st.empty()) {
		res += st.top();
		st.pop();
	}

	cout << res << '\n';

	return 0;
}