面试题整理12 求字符串括号最大深度子串

"a+b+((c+d)+(e+f))"，则结果为”c+d"。

分析： 一般算式会让人想起用栈分别存储操作数和符号值，但是本题目不适用，我写的代码中采用了类似于求最大连续子数组的解法，设置变量一个记录当前的括号深度，一个记录最大的括号深度，从字符串头开始遍历，当遍历到字符‘(‘时，当前括号深度加1，当遍历到字符‘)‘时，当前括号深度减1,；当当前括号深度大于最大括号深度时，将当前括号深度赋值给最大括号深度；当当前括号深度小于0时，将当前括号深度置0。算法复杂度O(n)。

代码如下：如有错误，请大家指正。

char* FindMostDeepExpression(const char* str)
{
	if(str == NULL)
		return NULL;
	int nLength = strlen(str);
	if(nLength < 2)
		return (char*)str;
	int maxDeepNum = 0;
	int tempDeepNum = 0;
	int startIndex = 0;
	int endIndex = nLength-1;
	bool isEnd = false; //标志是结束
	for(int i=0; i<nLength; ++i)
	{
		if(str[i] == ‘(‘)
		{
			++tempDeepNum;
			if(tempDeepNum > maxDeepNum )
			{
				maxDeepNum = tempDeepNum;
				isEnd = false;
				startIndex = i+1;
			}
		}else if( str[i] == ‘)‘)
		{
			if( tempDeepNum == maxDeepNum && !isEnd)
			{
				endIndex = i-1;
				isEnd = true;
			}
			-- tempDeepNum;
			if(tempDeepNum < 0)
			{
				tempDeepNum = 0;
			}
		}
	}
	char *result = new char[endIndex-startIndex+2];
	strncpy(result,str+startIndex,endIndex-startIndex+1);
	result[endIndex-startIndex+1] = ‘\0‘;
	return result;
}
void Test(char *testName, char* str,char* expectResult)
{
	if( testName!= NULL)
		printf("%s begins:\n",testName);
	if(expectResult != NULL)
		printf("expected result is %s \n",expectResult);

	
	char* result = FindMostDeepExpression(str);
	printf("the actual result is : %s \n",result);

}
void Test1()
{
	char* str = NULL;
	Test("Test1",str,NULL);
}
void Test2()
{
	char* str = "a+b";
	Test("Test2",str,"a+b");
}
void Test3()
{
	char* str = "a+b+((c+d)+(e+f))";
	Test("Test3",str,"c+d");
}
void Test4()
{
	char* str = "a+b+((c+d)+(e+f))";
	Test("Test3",str,"c+d");
}
void Test5()
{
	char* str = "a+(b+c)";
	Test("Test5",str,"b+c");
}
int main()
{
	
	Test1();
	Test2();
	Test3();
	Test4();
	system("pause");
}

面试题整理12 求字符串括号最大深度子串,布布扣,bubuko.com

面试题整理12 求字符串括号最大深度子串

原文：http://blog.csdn.net/kuaile123/article/details/20762103