NOI題庫(kù)2.2括號(hào)匹配分析與題解(C++)

1、問(wèn)題描述問(wèn)題描述 在某個(gè)字符串（長(zhǎng)度不超過(guò)在某個(gè)字符串（長(zhǎng)度不超過(guò)100）中有）中有左括號(hào)、右括號(hào)和大小寫字母；規(guī)定（與常左括號(hào)、右括號(hào)和大小寫字母；規(guī)定（與常見的算數(shù)式子一樣）見的算數(shù)式子一樣）任何一個(gè)左括號(hào)都從內(nèi)任何一個(gè)左括號(hào)都從內(nèi)到外與在它右邊且距離最近的右括號(hào)匹配到外與在它右邊且距離最近的右括號(hào)匹配。寫一個(gè)程序，找到寫一個(gè)程序，找到無(wú)法無(wú)法匹配的左括號(hào)和右括匹配的左括號(hào)和右括號(hào)，輸出原來(lái)字符串，并在下一行標(biāo)出不能號(hào)，輸出原來(lái)字符串，并在下一行標(biāo)出不能匹配的括號(hào)。不能匹配的左括號(hào)用匹配的括號(hào)。不能匹配的左括號(hào)用“$”標(biāo)注標(biāo)注,不能匹配的右括號(hào)用不能匹配的右括號(hào)用“?”標(biāo)注。標(biāo)注。輸出輸出

2、 輸入包括輸入包括多組數(shù)據(jù)多組數(shù)據(jù)，每組數(shù)據(jù)一行，包，每組數(shù)據(jù)一行，包含一個(gè)字符串，只包含左右括號(hào)和大小寫字含一個(gè)字符串，只包含左右括號(hào)和大小寫字母，字符串長(zhǎng)度不超過(guò)母，字符串長(zhǎng)度不超過(guò)100輸入輸入 對(duì)每組輸出數(shù)據(jù)，輸出兩行，第一行包對(duì)每組輸出數(shù)據(jù)，輸出兩行，第一行包含原始輸入字符，第二行由含原始輸入字符，第二行由$,?和和空格空格組組成，成，$和和?表示與之對(duì)應(yīng)的左括號(hào)和右括表示與之對(duì)應(yīng)的左括號(hào)和右括號(hào)不能匹配。號(hào)不能匹配。Sample inputSample output(ABCD(x)(rttyy()sss)(ABCD(x) $ )(rttyy()sss)( ? ?$問(wèn)題分析問(wèn)題分析

3、本題大致意思就是，對(duì)給定的多個(gè)字符本題大致意思就是，對(duì)給定的多個(gè)字符串，輸出其中無(wú)法匹配的括號(hào)標(biāo)記（左括號(hào)串，輸出其中無(wú)法匹配的括號(hào)標(biāo)記（左括號(hào)“$”，右括號(hào)右括號(hào)“?”），其他字符輸出空格，且），其他字符輸出空格，且位置嚴(yán)格按照原串。位置嚴(yán)格按照原串。 所以最重要的就是所以最重要的就是找出無(wú)法匹配的括號(hào)找出無(wú)法匹配的括號(hào)并標(biāo)記并標(biāo)記。問(wèn)題分析問(wèn)題分析 那么，如何找呢？那么，如何找呢？ 首先要清楚什么是匹配。題目說(shuō)，任何首先要清楚什么是匹配。題目說(shuō)，任何一個(gè)左括號(hào)都從內(nèi)到外與在它右邊且距離最一個(gè)左括號(hào)都從內(nèi)到外與在它右邊且距離最近的右括號(hào)匹配。近的右括號(hào)匹配。(aa()a)bb) ?下圖中，相

4、同顏色的括號(hào)匹配。下圖中，相同顏色的括號(hào)匹配。問(wèn)題分析問(wèn)題分析 很容易想到，可以假設(shè)一開始查找到的很容易想到，可以假設(shè)一開始查找到的“(”無(wú)法匹配，設(shè)為無(wú)法匹配，設(shè)為“$”，并記錄下它的下標(biāo)并記錄下它的下標(biāo)。其他字符直接設(shè)為空格。其他字符直接設(shè)為空格。 如此，直到查找到如此，直到查找到“)”，訪問(wèn)它和離它最訪問(wèn)它和離它最近的近的“(”的下標(biāo)，在原串中設(shè)為空格。的下標(biāo)，在原串中設(shè)為空格。 當(dāng)然，如果找到的當(dāng)然，如果找到的“(”下標(biāo)是一個(gè)不可能下標(biāo)是一個(gè)不可能的值，例如的值，例如-1，則該則該“)”無(wú)法匹配，在原串中無(wú)法匹配，在原串中設(shè)為設(shè)為“?”。(aa()a)bb)$? ?這樣就寫出了代碼：這

5、樣就寫出了代碼：string s;while(getline(cin, S) /讀入整行cout S endl; /輸出原串int left102,j=0; /left記錄所有(在S中的下標(biāo)，j只是指針memset(left, -1, sizeof(left); /初始化-1for(int i = 0; i = 0) /有匹配的左括號(hào)，下標(biāo)不為-1Sleftj = Si = ; /設(shè)空j-; /找上一個(gè)左括號(hào)elseSi = ?; /未匹配elseSi = ; /其他字符設(shè)空cout S endl; /輸出（已修改后的S）對(duì)嗎？對(duì)嗎？ 如果如果“(”下標(biāo)從下標(biāo)從left0開始存儲(chǔ)，當(dāng)?shù)陂_始存儲(chǔ)，當(dāng)?shù)谝粋€(gè)一個(gè)“(”匹配完后，匹配完后，j = -1，就會(huì)出現(xiàn)就會(huì)出現(xiàn)下標(biāo)下標(biāo)越界！越界！ 只要修改一句：只要修改一句：leftj+ = i;left+j