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

후위 표기식의 규칙

• 피연산자는 그냥 출력한다.
• 연산자의 경우, 우선 순위를 따지면서 스택에 push, pop 한다.
  • stack이 비어있으면 push
  • stack의 top이 현재 연산자보다 우선순위가 같거나 높으면 pop 후 출력
  • stack의 top이 현재 연산자보다 우선순위가 낮으면 push
  • '(' 인 경우, push
  • ')' 인 경우, '('을 만날 때 까지 pop
  • 여는 괄호와 닫는 괄호는 출력하지 않는다.

switch문을 써서 우선순위를 쉽게 고려할 수 있다. 처음에 switch를 쓰지 않아서 삽질을........ 코드가 너무 복잡해졌었다.

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

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	stack<char> s;
	string str;

	cin >> str;

	for (char c : str) {
		if (c >= 'A' && c <= 'Z') {
			cout << c;
		}
		else {
			switch (c) {
			case '(':
				s.push(c);
				break;
			case '*':
			case '/':
				while (!s.empty() && (s.top() == '*' || s.top() == '/')) {
					cout << s.top();
					s.pop();
				}
				s.push(c);
				break;
			case '+':
			case '-':
				while (!s.empty() && s.top() != '(') {
					cout << s.top();
					s.pop();
				}
				s.push(c);
				break;
			case ')':
				while (!s.empty() && s.top() != '(') {
					cout << s.top();
					s.pop();
				}
				s.pop();
			default: break;
			}
		}
	}

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

	return 0;
}