藍(lán)橋杯真題

在藍(lán)橋杯中有這樣一道題：給定一串字符，不超過100個(gè)字符，中間可能包括括號(hào)、數(shù)字、字母、標(biāo)點(diǎn)、空格，檢測字符中是否存在對(duì)應(yīng)的左括號(hào)和右括號(hào)，如果存在左括號(hào)和右括號(hào)，記錄下來輸出，統(tǒng)計(jì)一共出現(xiàn)了多少次成對(duì)括號(hào)。例如：輸入的字符內(nèi)容為（（234）（456））那么輸出就有三對(duì)括號(hào)分別對(duì)應(yīng)的位置是2和6;7和11;1和12以此類推。

這是C語言競賽中的題目，難度較高，現(xiàn)在把題目改簡單一點(diǎn)便于使用Scratch編程來實(shí)現(xiàn)。給定一個(gè)只包含左右括號(hào)的合法括號(hào)序列（只有括號(hào)沒有其他字符內(nèi)容），按從左到右的順序輸出每對(duì)配對(duì)的括號(hào)出現(xiàn)的位置，序列從1開始編號(hào)。例如：輸入（（）（））顯示結(jié)果應(yīng)為：1 6;2 3;4 5。

這道題目考查的知識(shí)點(diǎn)其實(shí)是順序棧的算法，棧是僅能在表尾進(jìn)行插入和刪除操作的線性表。在棧的尾部插入新元素又稱作進(jìn)棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素;從棧刪除元素又稱作出?；蛲藯?，它是把棧頂元素刪除，使得其相鄰的元素成為新的棧頂元素，用一個(gè)詞語來形容棧就是后進(jìn)先出。

針對(duì)這道題，利用列表，從左往右開始，遇到左括號(hào)，就把這個(gè)括號(hào)和對(duì)應(yīng)的位置記錄下來存入列表的第一位，當(dāng)遇到右括號(hào)，就取出前一個(gè)左括號(hào)的位置，這樣就完成了一次配對(duì)，然后把這個(gè)左括號(hào)從列表中刪除。下面給大家繪制一張簡單的示例圖，注意后進(jìn)先出原則：

第3個(gè)位置遇到了第1個(gè)右括號(hào)，那么前一個(gè)左括號(hào)是2，因此2和3配成一對(duì)，將這個(gè)左括號(hào)的2號(hào)位置從列表刪除。繼續(xù)向下尋找，在第5個(gè)位置遇到了第二個(gè)右括號(hào)，前一個(gè)左括號(hào)是4，因此4和5配成一對(duì)，將4位置的左括號(hào)刪除，最后一個(gè)右括號(hào)和位置1左括號(hào)進(jìn)行匹配。程序運(yùn)行結(jié)束。

在代碼中首先設(shè)置三個(gè)變量：答案、i、括號(hào)，一個(gè)列表：括號(hào)記錄。用戶根據(jù)提示信息（請(qǐng)輸入一組括號(hào)）輸入一串括號(hào)，將輸入內(nèi)容設(shè)置為回答。重復(fù)執(zhí)行括號(hào)的字符數(shù)的次數(shù)，在每次的執(zhí)過程中進(jìn)行判斷，當(dāng)括號(hào)內(nèi)的第i個(gè)字符=左括號(hào)，將左括號(hào)的位置記錄在括號(hào)記錄的列表中，如果括號(hào)內(nèi)的第i個(gè)字符=右括號(hào)，那么記錄下右括號(hào)的位置，同時(shí)從括號(hào)列表中提取左括號(hào)的位置進(jìn)行成對(duì)輸出，用分號(hào)隔開下一組數(shù)據(jù)。以此類推直到所有字符全部遍歷完成。

目前程序?qū)斎胱址笕渴抢ㄌ?hào)，這降低了難度。原題那樣還輸入了數(shù)字、空格等其他字符的情況，該如何只提取括號(hào)呢？你能想到簡單實(shí)現(xiàn)目標(biāo)的方法嗎？