1918 후위 표기식

문제의 조건이 너무 이해가 안되서 따로 찾아본 문제다..

단순한 규칙에 따라 문자열을 출력하면 되는데, 입력받은 문자열을 첫 번째부터 마지막까지 순회하며 다음과 같이 룰을 적용한다.

현재 문자를 C라 하면

1. C가 알파벳이라면 그냥 출력한다.
2. C가 *, / 이라면 스택에 남아있는 문자들 중에 자신과 같은 우선순위의 문자들을 모두 pop & 출력한 뒤, C를 push한다.
3. C가 +, - 이라면 스택에 남아있는 문자들 중에 자신과 같거나, 높은 순위의 문자들을 모두 pop & 출력한 뒤, C를 push한다.
4. C가 ( 이라면 C를 스택에 push한다.
5. C가 ) 이라면 (를 만날 때까지 pop & 출력한다.

처음에 우선순위를 어떻게 구현해야 하나 고민했었는데, 우선순위를 적용하는건, 스택에서 pop했을 때, if 분기의 순서로 간단하게 구현할 수 있다.

 

규칙을 설명하자면 다음과 같다.

1. 알파벳은 피연산자를 앞에 출력하는 후위 표기식의 방식을 따르기 때문에 그냥 출력한다.
2. *, / 는 +, -보다 우선순위가 높기 때문에 후위 표기식에서 +, -보다 앞에 있어야 한다.
3. +, -는 순서대로 연산만 하면 되기 때문에, 스택을 다 비우고 push한다.
4. ( 를 push하는 이유는 괄호 밖의 문자보다 높은 우선순위를 갖기 때문에 기억하기 위함이다.
5. 4에 따라 후위표기식에 괄호의 내용이 먼저 오도록 ( 만날 때까지 pop하게 된다.

정답코드

#include <iostream>
#include <stack>
#include <string>
using namespace std;
#define T s.top()
int main()
{
	string str;
	cin >> str;
	stack<char> s;
	
	for (const auto& c : str) {
		
		if (c >= 'A' && c <= 'Z') {
			cout << c;
		}
		else {
			if (c == '(') {
				s.push(c);
			}
			else if(c == '*' || c == '/') {
				while (!s.empty() && (T == '*' || T == '/')) {
					cout << T;
					s.pop();
				}
				s.push(c);
			}
			else if(c == '+' || c == '-'){
				while (!s.empty() && T != '(') {
					cout << T;
					s.pop();
				}
				s.push(c);
			}
			else if (c == ')') {
				while (!s.empty() && T != '(') {
					cout << T;
					s.pop();
				}
				s.pop();
			}
		}	
	}
	while (!s.empty()) {
		cout << T;
		s.pop();
	}
	return 0;
}