实验三 栈的基本操作
一、实验目的：
1、熟悉栈的定义和栈的基本操作
2、掌握顺序存储栈和链式栈的基本运算
3、加深对栈结构的理解，逐步培养解决实际问题的编程能力
二、实验内容
1、基础题
编写栈的基本操作
2、提高题
（1）进制转换
（2）表达式中括号的匹配问题
（3）表达式的运算问题
三、实验步骤
1、栈基本操作的实现
（1）顺序栈
typedef struct{
SElemType *base,*top;
int  StackSize;
}SqStack;
Status InitStack(SqStack &S)
{   S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    if(!S.base)
    {    cout<<endl<<"Allocate space failure !";
 return (ERROR);
    }
    S.top=S.base;
    S.stacksize=STACK_INIT_SIZE;
    return (OK);
} 
int StackEmpty(SqStack S)
{return S.base==S.top?1:0;}
Status GetTop(SqStack S,SElemType &e)
{   if(S.top==S.base)
    {    cout<<endl<<"It's a empty SqStack !";
 return (ERROR);
    }
    e=*(S.top-1);
    return (OK);
} 
Status Push(SqStack &S,SElemType e)
{   if(S.top-S.base>S.stacksize)
    {    S.base=(SElemType *)realloc(S.base,(S.stacksize+        STACKINCREMENT*sizeof(SElemType)));
 if(!S.base)
 {   cout<<endl<<"Overflow!";
     return (ERROR);
 }
 S.top=S.base+S.stacksize;
 S.stacksize+=STACKINCREMENT;
    }
    *S.top++=e;
    return (OK);
} 
Status Pop(SqStack &S,SElemType &e)
{    if(S.top==S.base)
     {    cout<<endl<<"It's a empty SqStack!";
  return (ERROR);
     }
     e=*--S.top;
     return (OK);
} 
(2) 链式栈
typedef struct SNode
{    SElemType data;
     struct SNode *next;
}SNode,*LinkStack;
2、提高题
（1）表达式匹配问题
需求分析：
问题：给定一表达式，判定表达式中括号“（”、“）”、“[”、“]”的匹配问题。
假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（〔〕（））或〔（〔 〕〔 〕）〕等为正确的格式，〔（ 〕）或（〔（ ））或 (( )])均为不正确的格式。检验括号是否匹配的方法可用"期待的急迫程度"这个概念来描述。
分析可能出现的不匹配的情况:
到来的右括弧非是所“期待”的; 
到来的是“不速之客”; 
直到结束，也没有到来所“期待”的。
Status matching(string &exp)
{
int i=0;
SElemType e;
int state = 1;
SqStack S;
InitStack(S);
while (exp[i] && state)
{
  switch  (exp[i])
  {
   case '(':
   case '[':{
Push(S, exp[i]);
i++;
break;
   }
   case ')':
   {
if (!StackEmpty(S))
  { GetTop(S,e);
if (e=='(')
 {
  Pop(S,e);
  i++;
  }
else
  state=0;
  }
   else
state = 0 ;
   break;
  }
   case  ']':
  {
if (!StackEmpty(S))
  { GetTop(S,e);
if (e=='[')
 {
  Pop(S,e);
  i++;
  }
else
  state=0;
  }
 else
state = 0 ;
 break;
   }
default :i++;
   }
  }
 if ( state && StackEmpty(S) ) return OK;
 else return ERROR;
}