C++ / 백준 / 1918 / 후위 표기식

문제

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

1918번: 후위 표기식

문제풀이

알파벳 순서는 서로 바뀌는 경우가 없으므로 입력받으면 바로 출력한다.

그 외의 경우는 스택을 이용하여 출력 순서를 정한다.

 

'+' 또는 '-'인 경우 다음 연산자를 생각해야 하므로 바로 출력을 하지 않고 스택에 push 한다.

그다음 ')'를 만나거나, '+' 또는 '-'가 연속으로 두 번 오는 경우에만 후위식으로 바꾸면 된다.

 

'*' 또는 '/' 인경우 바로 뒷 문자가 '('이 아닌 이상 바로 후위 표기식으로 바꾼다.

뒷문자가 '('인 경우는 먼저 괄호 안에 있는 중위 표기식을 후위 표기식으로 바꿔야 하므로 '*' 또는 '/' 연산을 스택에 push 한다.

 

괄호 '('인 경우 출력하면 안 되므로 스택에 push 한다. 괄호의 시작 부분을 알아야 하므로 pop은 나중에 한다.

 

괄호 ')'인 경우 괄호 '(' 부분까지 연산해야 하므로 '('이 나올 때까지 안에 있는 식을 후위 표기식으로 바꾼다.

괄호 '('을 발견하고 pop까지 했으면 이제 스택에 남은 부분을 확인해야 한다.

A*B*(C+D)인 경우 괄호 연산을 바꾸고 AB*와의 연산을 해야 된다.

 

마지막으로는 스택이 빌 때까지 남은 연산들을 출력하면 된다.

 

코드

#include <iostream>
#include <stack>
using namespace std;

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

	int idx(0);
	string input("");
	stack<char>s;
	cin >> input;


	for (idx = 0; idx < input.size(); ++idx) {
		if (input[idx] >= 'A' && input[idx] <= 'Z') {
			cout << input[idx];
		}
		else if (input[idx] == '(') {
			s.push('(');
		}
		else if (input[idx] == '*' || input[idx] == '/') {
			if (input[idx + 1] != '(') {
				cout << input[idx + 1] << input[idx];
				++idx;
			}
			else {
				s.push(input[idx]);
			}
		}
		else if (input[idx] == ')') {
			while (!s.empty()) {				
				if (s.top() != '(') {
					cout << s.top();
					s.pop();
				}
				else {
					s.pop();
					while (!s.empty() && (s.top() == '*' || s.top() == '/')) {
						cout << s.top();
						s.pop();
					}
					break;
				}
			}
		}
		else {			
			if (!s.empty() && (s.top() == '+' || s.top() == '-')) {
				while (!s.empty() && s.top() != '(') {
					cout << s.top();
					s.pop();
				}
				s.push(input[idx]);
			}
			else s.push(input[idx]);
		}
	}
	while (!s.empty()) {
		cout << s.top();
		s.pop();
	}
}