数据结构习题及答案

				◆3.19④ 假设一个算术表达式中可以包含三种括号：圆括号"(" 和
				")"，方括号"["和"]"和花括号"{"和"}"，且这三种括号可按任意的
				次序嵌套使用（如：…[…{…}…[…]…]…[…]…(…)…）。编写判别给定表达
				式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素
				为字符的顺序表中)。  
				
				实现下列函数：
				Status MatchCheck(SqList exp);                  
				/* 顺序表exp表示表达式；                        */
				/* 若exp中的括号配对，则返回TRUE，否则返回FALSE */
				
				顺序表类型定义如下：
				typedef struct {
				    ElemType *elem;
				    int       length;
				    int       listsize;
				} SqList;  // 顺序表
				
				Stack是一个已实现的栈。
				可使用的相关类型和函数：
				typedef char SElemType; // 栈Stack的元素类型
				Status InitStack(Stack &s);
				Status Push(Stack &s, SElemType e);
				Status Pop(Stack &s, SElemType &e);
				Status StackEmpty(Stack s);
				Status GetTop(Stack s, SElemType &e);
				Status MatchCheck(SqList exp)
				/* 顺序表exp表示表达式；                        */
				/* 若exp中的括号配对，则返回TRUE，否则返回FALSE */
				{
				  char c;
				  int i; 
				  Stack s;
				  InitStack(s);                          //建立栈s储存左括号
				  for(i=0;i				  {
				    if(exp.elem[i]=='('||exp.elem[i]=='['||exp.elem[i]=='{') Push(s,exp.elem[i]);
				    else if(exp.elem[i]==')'||exp.elem[i]==']'||exp.elem[i]=='}')
				    {
				      if(StackEmpty(s)) return FALSE;
				      GetTop(s,c);
				      if(exp.elem[i]==')'&&c!='(') return FALSE;
				      if(exp.elem[i]==']'&&c!='[') return FALSE;
				      if(exp.elem[i]=='}'&&c!='{') return FALSE; //必须与当前栈顶括号匹配
				      Pop(s,c);
				    }
				  }//for
				  if(!StackEmpty(s)) return FALSE;
				  return TRUE;
				
				
				}