[C++] BOJ 1918번 - 후위 표기식

📖 Problem

---

🔓 Solve

---

이전에 괄호가 없는 후위 표기식에 대한 문제를 푼 적이 있는데, 이는 스택의 원리를 이용하여 쉽게 풀 수 있었다.

그 기억을 떠올려 스택으로 똑같이 구현하려고 했지만, 괄호가 있기에 바로 스택에 넣거나 빼는 행위를 하지 못함을 알게 되었다.

따라서 먼저 식을 괄호가 없는 형태로 만들고, 이를 후위 표기식으로 변환하기로 했다.

이 로직에서 핵심이 되는 부분은 괄호가 없는 식에 대한 후위 표기식 변환이다.

왜나하면, 식을 가장 안쪽 괄호부터 찾아서, 이를 후위 표기식으로 바꾸고, 바뀐 후위 표기식을 하나의 문자로 보면 같은 함수를 이용해 모든 계산을 처리할 수 있기 때문이다.

즉, 로직의 흐름을 정리하면 다음과 같다.

1. 괄호가 없는 수식을 후위 표기식으로 바꾸는 함수를 정의한다. 이 함수는 string 타입의 vector을 인자로 받는데, 이는 계산이 된 수식인지 구분이 필요하기 때문이다. 하나의 string으로 인자를 받으면, 어느 부분이 계산이 완료된 덩어리인지 구분을 하지 못한다. 예를 들어 벡터의 내부가 { “ABC*+”, “D”, “E”, “/”, “-“ } 로 이루어져 있다고 하자. 이 때 “ABC*+”는 계산이 완료된 식으로, “D”, “E”와 같이 문자로 처리가 된다. 이외에 ”/”, “-“는 연산자로 처리가 된다.

2. 식의 모든 char들을 처음부터 스택에 넣어가며 진행한다.
3. 이후 닫는 괄호 ‘)’를 만나면 스택에서 거슬러 올라가 여는 괄호 ‘(‘를 만날 때까지 정의한 vector에 넣어가며 찾는다. 이후 여는 괄호를 만나면, vector을 뒤집고, 1번에서 정의한 함수를 이용해 후위 표기식으로 변환한다. 이후 변환된 식을 다시 스택에 넣는다.
4. 이렇게 문자열의 끝까지 탐색을 완료하면, 원본 스택에는 괄호가 없는 후위 표기식 덩어리들만 남게 된다. 이를 마지막으로 정의된 함수를 이용해 최종 후위 표기식으로 변환한다.

괄호가 없는 수식을 후위 표기식으로 바꾸는 로직은 다음과 같다.

1. string 타입의 스택을 한 개 정의한다.
2. 입력받은 vector를 앞에서부터 탐색한다.
3. ’*’ 또는 ‘/’의 경우 그 즉시 처리한다. stack.top()과 vec[index + 1]의 값을 이용해 인접한 수와 계산을 처리하고, 다시 스택에 삽입한다.
4. 반복문을 한 차례 돌면, stack에는 ’+’, ‘-‘, 후위 표기식 덩어리들이 남게 된다.
5. 다시 한 번 stack이 빌 때까지 반복문을 돈다. 이 때 ‘+’, ‘-‘만 남아 있으므로 앞에서부터 차례대로 붙여주며 진행하면 된다.
6. 완성된 string을 반환한다.

💻 Code

---

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

using namespace std;

string calc_no_bracket(const vector<string>& vec) {
	// calculation expression which doesn't have bracket

	stack<string> result_st;

	for (int index = 0; index < vec.size(); index++) {
		if (vec[index] == "*" || vec[index] == "/") {
			string str_1 = result_st.top();
			result_st.pop();
			result_st.push(str_1 + vec[index + 1] + vec[index]);
			index++;
		}

		else {
			string str1;
			str1 += vec[index];
			result_st.push(str1);
		}
	}

	// dispose of '+' and '-'
	string result;

	while (result_st.size() != 1) {
		string str_1 = result_st.top();
		result_st.pop();
		string op = result_st.top();
		result_st.pop();

		result = str_1 + op + result;
	}
	result = result_st.top() + result;

	return result;
}


int main() {
	string s;
	cin >> s;

	stack<string> st;

	for (int index = 0; index < s.length(); index++) {
		// case 1 : ')'
		if (s[index] == ')') {
			vector<string> v;

			while (true) {
				string str_in_st = st.top();
				st.pop();

				if (str_in_st == "(") {
					break;
				}
				else {
					v.push_back(str_in_st);
				}
			}
			reverse(v.begin(), v.end());

			st.push(calc_no_bracket(v));
		}

		// case 2 : just push
		else {
			string str;
			str += s[index];
			st.push(str);
		}
	}


	vector<string> result;
	while (!st.empty()) {
		result.push_back(st.top());
		st.pop();
	}

	reverse(result.begin(), result.end());

	cout << calc_no_bracket(result) << endl;

}

괄호로 인해 처음에 당황을 많이 했는데, 어차피 무조건 괄호의 가장 안쪽은 괄호가 없는 일반식이다. 이를 깨닫고 가장 안쪽부터 괄호로 둘러싸인 식을 풀며 나오는 방식을 생각해내는게 풀이의 핵심인 것 같다.

---

---

⚡개인적으로 공부하면서 포스팅한 글입니다. 오류가 있는 경우 지적해주시면 감사하겠습니다!⚡