題目：求一個表達(dá)式字符串中括號層次最深的第一個表達(dá)式，如表達(dá)式 

"a+b+((c+d)+(e+f))"，則結(jié)果為”c+d"。

分析： 一般算式會讓人想起用棧分別存儲操作數(shù)和符號值，但是本題目不適用，我寫的代碼中采用了類似于求最大連續(xù)子數(shù)組的解法，設(shè)置變量一個記錄當(dāng)前的括號深度，一個記錄最大的括號深度，從字符串頭開始遍歷，當(dāng)遍歷到字符‘('時，當(dāng)前括號深度加1，當(dāng)遍歷到字符‘)'時，當(dāng)前括號深度減1,；當(dāng)當(dāng)前括號深度大于最大括號深度時，將當(dāng)前括號深度賦值給最大括號深度；當(dāng)當(dāng)前括號深度小于0時，將當(dāng)前括號深度置0。算法復(fù)雜度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; //標(biāo)志是結(jié)束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"); }

總結(jié)

以上是生活随笔為你收集整理的面试题整理12 求字符串括号最大深度子串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。