백준 1918: 후위 표기식

문제 요약

중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

문제 분류

• 자료 구조
• 스택

문제 풀이

기본 골자는 모든 연산자는 스택에 쌓고, 문자는 출력하게 되는데, 각 연산자마다 해야하는 연산이 달라진다.

'('문자를 만났을때는 단순히 스택에 쌓는것만으로 되지만, ')'문자를 만났을때는 스택의 top이 '('가 될 때까지 pop하며 출력후, 마지막 '('을 pop해준다.

*나 /는 +나 -보다 연산의 우선순위보다 높으므로 먼저 출력하여 처리해주어야 하고,

반대로 +나 -는 우선순위가 떨어지기 때문에 나중에 출력해주어야 한다.

이 외의 문자('A', 'B' 등)은 그대로 출력하면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

int main()
{
	stack<char> s;
	string in;
	cin >> in;
	for (int i = 0; i < in.length(); i++) {
		if (in[i] == '*' || in[i] == '/') {
			while (!s.empty()) {
				if (s.top() == '(' || s.top() == '+' || s.top() == '-') break;
				cout << s.top();
				s.pop();
			}
			s.push(in[i]);
		}
		else if (in[i] == '+' || in[i] == '-') {
			while (!s.empty()) {
				if (s.top() == '(') break;
				cout << s.top();
				s.pop();
			}
			s.push(in[i]);
		}
		else if (in[i] == '(') s.push(in[i]);
		else if (in[i] == ')') {
			while (!s.empty()) {
				if (s.top() == '(') {
					s.pop();
					break;
				}
				cout << s.top();
				s.pop();
			}
		}
		else cout << in[i];
	}
	while (!s.empty()) {
		cout << s.top();
		s.pop();
	}
	return 0;
}