[백준 1918] 후위 표기식

문제

백준 1918

유형

• 자료구조
• 스택

풀이

1. *, / 이후에 숫자가 나오면 바로 계산
2. )가 나오면 (가 나올때 까지 계산
3. 위 연산 후 +, - 계산

처음에는 위의 방식으로 구현을 하였지만 예외처리를 해야할 경우가 너무 많아서 구현에 어려움이 있었다. 그래서 다른 풀이를 참조하였다.

참조한 풀이법은 아래와 같다.

1. 숫자는 바로 출력
2. ( 스택에 푸쉬
3. )이면 (가 나올 때까지 스택에서 뽑아냄
4. -, + 이면 (가 아닐 때까지 스택에서 뽑아냄
5. *, -이면 (, -, +가 아니면 스택에서 뽑아냄

코드로 구현은 간단하게 된다.

코드

#include <bits/stdc++.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;


int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	string x;
	cin >> x;
	
	stack<string> s;
	for (int i = 0; i < x.length(); i++) {
		if (x[i] == '(') s.push(string(1, x[i]));
		else if (x[i] == ')') {
			while (!s.empty() && s.top() != "(") {
				cout << s.top();  s.pop();
			}
			s.pop();
		}
		else if (x[i] == '*' || x[i] == '/') {
			while (!s.empty() && (s.top() == "*" || s.top() == "/")) {
				cout << s.top(); s.pop();
			}
			s.push(string(1, x[i]));
		}
		else if (x[i] == '+' || x[i] == '-') {
			while (!s.empty() && s.top() != "(") {
				cout << s.top(); s.pop();
			}
			s.push(string(1, x[i]));
		}
		else cout << x[i];
	}

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

	return 0;
}