문제 출처

1. 문제설명

  • 중위 표기식이 주어졌을 때 후위 표기식으로 변경하라

  • 문제 분류

    • Data Structure, Stack


2. 알고리즘 설계

  • 문제를 보자마자 스택을 이용해야 된다는 생각이 들었다.
  • 규칙을 조금 생각해보면, 문자는 그냥 출력하면 된다.
  • 연산자 우선순위를 잘 고려해보자
    • 우선순위 : 괄호 -> 곱셈/나눗셈 -> 덧셈/뺄셈
    • 괄호
      • 여는 괄호 : 스택에 그냥 넣는다.
      • 닫는 괄호 : 스택의 top이 여는 괄호가 될 때까지 스택 원소를 꺼내 출력한다.
    • 곱셈/나눗셈
      • 스택의 top이 곱셈 또는 나눗셈이 될 때까지 스택 원소를 꺼내 출력한다.
    • 덧셈/뺄셈
      • 이 부분이 조금 헷갈릴 수 있겠다.
      • 기본적으로 우선순위가 가장 뒤지만, 괄호 안에 있다면 우선 되어야 한다.
      • 스택의 top이 여는 괄호가 될 때까지 스택 원소를 꺼내 출력한다.
  • 이제 스택에 남은 걸 전부 출력해주면 된다.


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

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

	string s;
	cin >> s;

	stack<char> st;

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

	return 0;
}