문자열 조작 1 - 재귀함수

주어진 괄호 문자열을 '올바른 괄호 문자열' 형태로 만든 후 출력

 

주어진 괄호 문자열을 정해진 알고리즘 대로 구현 할 수 있는지, 재귀함수를 구현 할 수 있는지를 묻는 문제다.

입출력 예제

)( => ()

()))((() => ()(())()

 

'(', ')'의 개수가 일치하는 문자열은 '균형잡힌 괄호 문자열'

균형잡힌 괄호 문자열에서 괄호들이 올바르게 짝이 맞으면 '올바른 괄호 문자열'

 

#include <string>
#include <vector>

using namespace std;

bool IsPerfectPair(string p)
{
	int value = 0;
	for(int i = 0; i < p.length(); ++i)	
	{
		if(p[i] == '(')
			value++;
		else
			value--;

		if(value < 0)
			break;
	}

	return value == 0 ? true : false;
}

string solution(string p) {
    	string answer = "";
	if(p.empty())
		return answer; 

	int len = p.length();
	int openCount = 0;
	int closeCount = 0;

	string u = "";
	string v = "";

	for(int i = 0; i < len; ++i)
	{
		if(p[i] == '(')
			openCount++;
		else if(p[i] == ')')
			closeCount++;

		if(openCount == closeCount)
		{
			u = p.substr(0, i+1);
			v = p.substr(i+1);
			break;
		}
	}

	if(IsPerfectPair(u))
	{
		answer += u + solution(v);
	}
	else
	{
		answer = "(";	
		answer += solution(v);
		answer += ")";
		u = u.substr(1, u.length()-2);
		for(int i = 0; i < u.length(); ++i)
		{
			if(u[i] == '(')
				u[i] = ')';
			else
				u[i] = '(';
		}

		answer += u;
	}

	return answer;
}