閱讀以下說明和C函數(shù),填補C函數(shù)中的空缺(1)~(5),將解答寫在答題紙的對應欄內(nèi)。
【說明】
假設(shè)一個算術(shù)表達式中可以包含以下三種括號:“(”和“)”、"[”和“]”、“{”和“}”,并且這三種括號可以按照任意的次序嵌套使用。
下面僅考慮表達式中括號的匹配關(guān)系,其他問題暫時忽略。例如,表達式“[a.(b.5)】*c【{}】”中的括號是完全匹配的,而表達式“【a-(b-5]))*c”中的括號不是完全匹配的,因為“(”與“】”不能匹配,而且多了一個“)”,即缺少一個與“)”相匹配的“(”。
函數(shù)ifmatched (char expr[])的功能是用棧來判斷表達式中的括號是否匹配,表達式以字符串的形式存儲在字符數(shù)組expr中。若表達式中的括號完全匹配,則該函數(shù)的返回值為Matched,否則返回值為Mismatched。
該函數(shù)的處理思路如下:
(1)設(shè)置一個初始為空的棧,從左至右掃描表達式。
(2)若遇上左括號,則令其入棧;若遇上右括號,則需要與棧頂?shù)淖罄ㄌ栠M行匹配。
(3)若所遇到的右括號能與棧頂?shù)淖罄ㄌ柵鋵?,則令棧頂?shù)淖罄ㄌ柍鰲?,然后繼續(xù)匹配過程;否則返回Mismatched,結(jié)束判斷過程。
(4)若表達式掃描結(jié)束,同時棧變?yōu)榭?,則說明表達式中的括號能完全匹配,返回Matched。
函數(shù)ifMatched中用到了兩種用戶自定義數(shù)據(jù)類型BOOL和STACK,其中,BOOL類型的定義如下:
typedef enum {Mismatched, Matched}BOOL;
STACK(即棧類型)的定義省略,棧的基本操作的函數(shù)原型說明如下:
void InitStack(STACK *S):初始化一個空棧。
void Push(STACK *S,char e):將一個字符壓棧,棧中元素數(shù)目增1。
void Pop(STACK *S):棧頂元素出棧,棧中元素數(shù)目減1。
char Top(STACK S):返回非空棧S的棧頂元素值,棧中元素數(shù)目不變。
int IsEmpty(STACK S):若S是空棧,則返回1,否則返回0。
【C 函數(shù)】
BOOL ifMatched (char expr[ ])
{
char *cptr; /* cptr 指向表達式中的字符*/
STACK S;
char e;
InitStack(&S} ; /*構(gòu)造一個空棧*/
for(cptr = expr; *cptr!= '\0' (1) {
if ( *cptr== ' (' || *cptr ==' [' , || *cptr ==' {' )
(2);
else
if ( *cptr==')' || *cptr== ']' || *cptr=='}' ) {
if (IsEmpty (S) )
return Mismatched;
e =(3) ; /*取棧頂?shù)淖罄ㄌ?/
if ( *cptr ==')' ,&& e!=' (' ) return Mismatched;
if ( *cptr ==']' && e!=' [' ) return Mismatched;
if ( *cptr ==')' && e!='{' )return Mismatched;
(4) ; /*梭頂?shù)淖罄ㄌ柍鲂?/
}
}
if ((5)) return Matched;
return Mismatched;
}