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

 

1918번: 후위 표기식

지난 1학기에 자료구조 수업에서 스택을 배우면서 같이 배웠던 내용이다.

강의자료 PDF를 다시 열어 참고했다.

위에 설명된대로 코드를 작성하면 AC를 받는다.

나는 첫 번째 제출에서 오타가 생겨서 한 번 더 시도해서 AC를 받았다.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	stack<char> stk;
	string expr, ans;
	cin >> expr;
	for (auto& e : expr) {
		switch (e) {
		case '(':
			stk.push(e);
			break;
		case ')':
			while (!stk.empty() && stk.top() != '(') {
				ans.push_back(stk.top());
				stk.pop();
			}
			stk.pop();
			break;
		case '*':
		case '/':
			while (!stk.empty() && (stk.top() == '*' || stk.top() == '/')) {
				ans.push_back(stk.top());
				stk.pop();
			}
			stk.push(e);
			break;
		case '+':
		case '-':
			while (!stk.empty() && (stk.top() == '*' || stk.top() == '/' || stk.top() == '+' || stk.top() == '-')) {
				ans.push_back(stk.top());
				stk.pop();
			}
			stk.push(e);
			break;
		default:
			ans.push_back(e);
			break;
		}
	}
	while (!stk.empty()) {
		ans.push_back(stk.top());
		stk.pop();
	}
	cout << ans << EL;

	return 0;
}

위에서 +, -가 나오는 부분에 while 조건이 길다.

현재 스택의 top에 있는 값이 연산자 우선순위가 높거나 같으면 출력하고 pop하는건데,

사실상 모든 연산자를 pop하는 것이므로, 다음과 같이 표현하면 간결해진다.

while(!stk.empty() && stk.top != '(') {
	// something
}