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

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

1918번: 후위 표기식

---

 문제 풀이

스택의 대표적인 문제이다!

피연산자는 단순히 스트링에 추가해주면 된다.

연산자인 '+', '-', '/', '*', '(', ')' 에 대해선 추가적인 작업이 필요하다.

 1. '(' 은 무조건 스택에 push 한다.

 2. 각 연산자마다 우선순위가 존재한다. '*', '/' 이 가장 높고, 괄호들이 가장 낮다.

 3. 스택의 top보다 지금 확인하는 연산자의 우선순위가 높다면 그냥 스택에 push 한다.

 4. 반대로 스택의 top이 우선 순위가 더 높다면 자신보다 낮은 연산자가 나올 때 까지 pop 한다.

 5. ')'가 나오면 '('이 나올 때까지 pop 해준다.

이후 반복이 끝나면 스택이 남아있는 값을 모두 pop 해준다.

 느낀 점

자료구조 수업 때 배웠던 내용임에도 불구하고 막상 구현하려니까 까다로웠다. 구현하기 이전에 다시 공부하고 구현했다. 피연산자인지 확인할 때 isalpha 함수를 사용했는데 백준에 제출할 때는 정상적으로 사용되지 않는다.. 왜 그런지 모르겠다..

 코드

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

using namespace std;

string str, ans = "";
stack<char> s;

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

	cin >> str;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] >= 'A' && str[i] <= 'Z') ans += str[i];
		else {
			switch (str[i]) {
			case '(' :
				s.push(str[i]);
				break;
			case '*':
			case '/':
				while (!s.empty() && (s.top() == '*' || s.top() == '/')) {
					ans += s.top();
					s.pop();
				}
				s.push(str[i]);
				break;
			case '+':
			case '-':
				while (!s.empty() && s.top() != '(') {
					ans += s.top();
					s.pop();
				}
				s.push(str[i]);
				break;
			case ')':
				while (!s.empty() && s.top() != '(') {
					ans += s.top();
					s.pop();
				}
				s.pop();
				break;
			}
		}
	}

	while (!s.empty()) {
		ans += s.top();
		s.pop();
	}

	cout << ans << "\n";
}