藍(lán)橋杯真題

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

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

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

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

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

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

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