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