3.19.c

数据结构习题及答案

◆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<exp.length;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;


}