[c++ 백준 문제풀이] 백준 1918: 후위표기식

 

> 풀이 전략

- stack 을 활용하여 연산자 임시 저장

- 연산자의 우선순위를 정의해, 우선순위에 따라 연산자를 임시 저장한 stack을 비우고 채움

  우선순위 >>>>     (      >>>>>>>      +,-     >>>>>>>>    *,/  

- 괄호가 등장하면, 괄호 안에서 독립적으로 같은 규칙이 적용 ( 닫는 괄호가 나오면 전부 토해내야함 )

- vector로 결과값 저장하는 배열 구현

 

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

int checkRank(char a) {
	if (a == '(') return 0;
	else if (a == '+' || a == '-') return 1;
	else return 2;
}

int main() {
	std::string in;
	std::cin >> in;

	std::vector<char> postfixList;
	std::stack<char> signList;

	for (char c : in) {
		if (c == '(') {
			signList.push(c);
		}
		else if (c == ')'){
			while (signList.top() != '(') {
				postfixList.push_back(signList.top());
				signList.pop();
			}
			signList.pop();
		}
		else if (c == '+' || c == '-' || c == '*' || c == '/') {
			if(signList.empty()) signList.push(c);
			else if (checkRank(signList.top()) >= checkRank(c)) {
				while (!signList.empty() && checkRank(signList.top()) >= checkRank(c)) {
					postfixList.push_back(signList.top());
					signList.pop();
				}
				signList.push(c);
			}
			else {
				signList.push(c);
			}
		}
		else {
			postfixList.push_back(c);
		}
	}
	while (!signList.empty()) { 
		postfixList.push_back(signList.top());
		signList.pop(); 
	}

	for (char a : postfixList) {
		std::cout << a;
	}
	std::cout << "\n";
}