在藍(lán)橋杯中有這樣一道題:給定一串字符,不超過100個字符,中間可能包括括號、數(shù)字、字母、標(biāo)點(diǎn)、空格,檢測字符中是否存在對應(yīng)的左括號和右括號,如果存在左括號和右括號,記錄下來輸出,統(tǒng)計(jì)一共出現(xiàn)了多少次成對括號。例如:輸入的字符內(nèi)容為((234)(456))那么輸出就有三對括號分別對應(yīng)的位置是2和6;7和11;1和12以此類推。
這是C語言競賽中的題目,難度較高,現(xiàn)在把題目改簡單一點(diǎn)便于使用Scratch編程來實(shí)現(xiàn)。給定一個只包含左右括號的合法括號序列(只有括號沒有其他字符內(nèi)容),按從左到右的順序輸出每對配對的括號出現(xiàn)的位置,序列從1開始編號。例如:輸入(()())顯示結(jié)果應(yīng)為:1 6;2 3;4 5。
這道題目考查的知識點(diǎn)其實(shí)是順序棧的算法,棧是僅能在表尾進(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)行匹配。程序運(yù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ù)字、空格等其他字符的情況,該如何只提取括號呢?你能想到簡單實(shí)現(xiàn)目標(biāo)的方法嗎?