阅读以下说明和C函数,填补C函数中的空缺(1)~(5),将解答写在对应栏内。
[说明]
假设一个算术表达式中可以包含以下三种括号:“(”和“)”、“[”和“]”及“”和“”,并且这三种括号可以按照任意的次序嵌套使用。
下面仪考虑表达式中括号的匹配关系,其他问题暂时忽略。例如,表达式[a-(b-5)*c[]中的括号是完全匹配的,而表达式[a-(b-5]))*c中的括号不是完全匹配的,因为“(”与“]”不能匹配,而且多了一个“)”,即缺少一个与“)”相匹配的“(”。
函数if Matched(char expr[])的功能是用栈来判断表达式中的括号是否匹配,表达式以字符串的形式存储在字符数组expr中。若表达式中的括号完全匹配,则该函数的返回值为Matched,否则返回值为Mismatched。
该函数的处理思路如下:
(1)设置一个初始为空的栈,从左至右扫描表达式。
(2)若遇上左括号,则令其入栈;若遇上右括号,则需要与栈顶的左括号进行匹配。
(3)若所遇到的右括号能与栈顶的左括号配对,则令栈顶的左括号出栈,然后继续匹配过程;否则返回Mismatched,结束判断过程。
(4)若表达式扫描结束,同时栈变为空,则说明表达式中的括号能完全匹配,返回Matched。
函数if Matched中用到了两种用户白定义数据类型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;
(4)处应填()。