BOJ - 정규형 (4882번)

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

 

스택을 활용하여 문제를 해결했습니다.

 

이 문제에서 주의해야 할 점은 "가장 낮은 레벨에 있는 트리는 AND 트리이다." 라는 것 입니다.

보통의 트리 구조에서 낮은 레벨이라 하면 루트노드의 레벨을 뜻하지만, 보통의 트리 구조에서 가장 높은 레벨의 트리가 이 문제에서는 가장 낮은 레벨이 됩니다.

 

주어진 트리의 최대 레벨을 구하고 닫는 괄호가 나올 시, AND와 OR을 구분하는 과정을 통해 답을 도출해 나아갔습니다.

 

위의 특징과 입력으로 주어지는 괄호들을 적절히 조합하여 아래의 코드를 작성하였습니다.

#include <iostream>
#include <map>
#include <string>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
int getMaxLevel(string str);
int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int leftCount = 0, andHasFalse = 0, orHasTrue = 0,
		progressCount = 1, maxLevel = 0;
	string input;
	while (true)
	{
		stack<char>st;
		cin >> input;
		if (input == "()")
			break;
		leftCount = 0;
		maxLevel = getMaxLevel(input);
		for (int i = 0; i < input.length(); i++)
		{
			andHasFalse = 0, orHasTrue = 0;
			if (input[i] == '(') {
				leftCount++;
				st.push(input[i]);
			}
			else if (input[i] == 'F' || input[i] == 'T') {
				st.push(input[i]);
			}
			else {
				string temp = "";
				while (st.top() != '(') {
					temp.push_back(st.top());
					st.pop();
				}
				st.pop();
				if ((maxLevel - leftCount) % 2 == 0) {
					//AND연산
					for (int i = 0; i < temp.length(); i++)
					{
						if (temp[i] == 'F') {
							andHasFalse = 1;
							st.push('F');
							break;
						}
					}
					if (!andHasFalse)
						st.push('T');
				}
				else {
					//OR연산
					for (int i = 0; i < temp.length(); i++)
					{
						if (temp[i] == 'T') {
							orHasTrue = 1;
							st.push('T');
							break;
						}
					}
					if (!orHasTrue)
						st.push('F');
				}
				leftCount--;
			}
		}
		if (st.top() == 'T')
			cout << progressCount << ". true\n";
		else
			cout << progressCount << ". false\n";
		progressCount++;
	}
	return 0;
}
int getMaxLevel(string str) {
	int leftCnt = 0, maxLevel = 0;
	for (int i = 0; i < str.length(); i++)
	{
		if (str[i] == '(') {
			leftCnt++;
			maxLevel = max(maxLevel, leftCnt);
		}
		else if (str[i] == ')')
			leftCnt--;
	}
	return maxLevel;
}