判断圆括号是否配对用C语言如何实现
栈的定义
栈（Stack）又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。人们把此端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把另一端称为栈底。 向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。
在日常生活中，有许多类似栈的例子，如刷洗盘子时，依次把每个洗净的盘子放到洗好的盘子上，相当于进栈；取用盘子时，从一摞盘子上一个接一个地向下拿，相当于出栈。 又如向枪支弹夹里装子弹时，子弹被一个接一个地压入，则为进栈；射击...全部
栈的定义
栈（Stack）又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。人们把此端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把另一端称为栈底。
向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。
在日常生活中，有许多类似栈的例子，如刷洗盘子时，依次把每个洗净的盘子放到洗好的盘子上，相当于进栈；取用盘子时，从一摞盘子上一个接一个地向下拿，相当于出栈。
又如向枪支弹夹里装子弹时，子弹被一个接一个地压入，则为进栈；射击时子弹总是从顶部一个接一个地被射出，此为子弹出栈。
由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先出栈，所以又把栈称为后进先出表(Last In First Out, 简称LIFO)。
例如，假定一个栈S为（a,b,c），其中字符c的一端为栈顶，字符c为栈顶元素。若向S压入一个元素d，则S变为（a,b,c,d），此时字符d为栈顶元素；若接着从栈S中依次删除两个元素，则首先删除的是元素d，接着删除的使元素c，栈S变为（a,b），栈顶元素为b。
2。 栈的存储结构
栈既然是一种线性表，所以线性表的顺序存储和链接存储结构同样适用于栈。
(1) 栈的顺序存储结构
栈的顺序存储结构同样需要使用一个数组和一个整型变量来实现，利用数组来顺序存储栈中的所有元素，利用整型变量来存储栈顶元素的下标位置。
假定栈数组用 stack[StackMaxSize]表示，指示栈顶位置的整型变量用top表示，则元素类型为ElemType的栈的顺序存储类型可定义为：
ElemType stack[StackMaxSize];
int top;
其中，StackMaxSize为一个整型全局常量，需事先通过const语句定义，由它确定顺序栈（即顺序存储的栈）的最大深度，又称为长度，即栈最多能够存储的元素个数；由于top用来指示栈顶元素的位置，所以把它称为栈顶指针。
栈的顺序存储结构同样可以定义在一个记录类型中，假定该记录类型用Stack表示，则定义为：
struct Stack {
ElemType stack[StackMaxSize];
int top;
};
在顺序存储的栈中，top的值为-1表示栈空，每次向栈中压入一个元素时，首先使top增1，用以指示新的栈顶位置，然后再把元素赋值到这个位置上，每次从栈中弹出一个元素时，首先取出栈顶元素，然后使top减1，指示前一个元素成为新的栈顶元素。
由此可知，对顺序栈的插入和删除运算相当于是在顺序表（即顺序存储的线性表）的表尾进行的，其时间复杂度为O(1)。
设一个栈S为（a,b,c,d,e），对应的顺序存储结构如图4-1(a)所示。
若向S中插入一个元素f，则对应如图4-1(b)所示。若接着执行两次出栈操作后，则栈S对应如图4-1(c)所示。若依次使栈S中的所有元素出栈，则s变为空，如图4-1(d)所示。在图4-1中栈是垂直画出的，并且使下标编号向上递增，这样可以形象地表示出栈顶在上，栈底在下。
图4-1 栈的顺序存储结构及操作过程
在一个顺序栈中，若top已经指向了StackMaxSize-1的位置，则表示栈满，若top的值已经等于-1，则表示栈空。
向一个满栈插入元素和从一个空栈删除元素都是不允许的，应该停止程序运行或进行特别处理。
(2) 栈的链接存储结构
栈的链接存储结构与线性表的链接存储结构相同，是通过由结点构成的单链表实现的，此时表头指针被称为栈顶指针，由栈顶指针指向的表头结点被称为栈顶结点，整个单链表被称为链栈，即链接存储的栈。
当向一个链栈插入元素时，是把该元素插入到栈顶，即使该元素结点的指针域指向原来的栈顶结点，而栈顶指针则修改为指向该元素结点，使该结点成为新的栈顶结点。当从一个链栈中删除元素时，是把栈顶元素结点删除掉，即取出栈顶元素后，使栈顶指针指向原栈顶结点的后继结点。
由此可知，对链栈的插入和删除操作是在单链表的表头进行的，其时间复杂度为O(1)。
设一个栈为（a,b,c），当采用链接存储时，对应的存储结构示意图如图4-2(a)所示，其中HS表示栈顶指针，其值为存储元素c结点的地址。
当向这个栈插入一个元素d后，对应如图4-2(b)所示。当从这个栈依次删除两个元素后，对应如图4-2(c)所示。当链栈中的所有元素全部出栈后，栈顶指针HS 的值为空，即常量NULL所表示的数值0。
图4-2 栈的链接存储结构及操作过程
3。 栈的抽象数据类型
栈的抽象数据类型中的数据部分为具有ElemType元素类型的一个栈，它可以采用任一种存储结构实现；操作部分包括元素进栈、出栈、读取栈顶元素、检查栈是否为空等。
下面给出栈的抽象数据类型的具体定义。
ADT STACK is
Data:
采用顺序或链接方式存储的栈，假定其存储类型用StackType
标识符表示。
Operation:
void InitStack(StackType& S);
// 初始化栈S，即把它置为空
void ClearStack(StackType& S);
// 清除栈S中的所有元素，使之成为一个空栈
int StackEmpty(StackType& S);
// 判断S是否为空，若是则返回1，否则返回0
ElemType Peek(StackType& S)
// 返回S的栈顶元素，但不移动栈顶指针
void Push(StackType& S, const ElemType& item)
// 元素item进栈，即插入到栈顶
ElemType Pop(StackType& S)
// 删除栈顶元素并返回之
int StackFull(Stack& S)
// 若栈已满则返回1，否则返回0，此函数为顺
// 序存储的栈所特有
end STACK
对于判断栈是否为空和返回栈顶元素的两种操作，由于它们不改变栈的状态，所以可在参数类型说明前使用常量定义符const。
假定栈a的元素类型为int，下面给出调用上述栈操作的一些例子。
(1) InitStack(a); // 把栈a置空
(2) Push(a,35); // 元素35进栈
(3) int x=48; Push(a,x); // 48进栈
(4) Push(a,x/2); // x除以2的值24进栈
(5) x=Pop(a); // 栈顶元素24退栈并赋给x
(6) x=Peek(a); // 读取栈顶元素48并赋给x
(7) Pop(a); // 栈顶元素48退栈
(8) StackEmpty(a); // 因栈非空，应返回0
(9) coutnext;
delete cp;
cp=np;
}
HS=NULL; // 置链栈为空
}
(3) 检查链栈是否为空
int StackEmpty(LNode* HS)
// HS为值参或引用形参均可
{
return HS==NULL;
}
(4) 读取栈顶元素
ElemType Peek(LNode* HS) // HS为值参或引用形参均可
{
if(HS==NULL) {
cerrdata;
}
(5) 向链栈中插入一个元素
void Push(LNode*& HS, const ElemType& item)
{
// 为插入元素获取动态结点
LNode* newptr= new LNode;
if(newptr==NULL) {
cerrdata=item;
// 向栈顶插入新结点
newptr->next=HS;
HS=newptr;
}
(6) 从链栈中删除一个元素
ElemType Pop(LNode*& HS)
{
if(HS==NULL) {
cerrnext; // 使栈顶指针指向其后继结点
ElemType temp=p->data; // 暂存原栈顶元素
delete p; // 回收原栈顶结点
return temp; // 返回原栈顶元素
}
5。
栈的简单应用举例
例1。 从键盘上输入一批整数，然后按照相反的次序打印出来。
根据题意可知，后输入的整数将先被打印出来，这正好符合栈的后进先出的特点。所以此题很容易用栈来解决。
参考程序如下：
#include
#include
const int StackMaxSize=30;
typedef int ElemType; // 定义元素类型为整型
struct Stack {
ElemType stack[StackMaxSize];
int top;
};
#include"stack。
h"
// 假定对顺序栈操作的算法已经存于"stack。
h"头文件中
void main()
{
Stack a;
InitStack(a);
int x;
cin>>x;
while(x!=-1) {
// 假定用-1作为终止键盘输入的标志，输入的整数个数
// 不能超过StackMaxSize所规定的值
Push(a,x);
cin>>x;
}
while(!StackEmpty(a)) // 栈不为空时依次退栈打印出来
cout>ch) // 顺序扫描文件中的每一个字符
{
if(ch==39) { // 单引号内的字符不参与配对比较
while(ifstr>>ch)
if(ch==39) // 39为单引号的ASCII值
break;
if(!ifstr)
return 0;
}
else if(ch==34) { // 双引号内的字符不参与配对比较
while(ifstr>>ch)
if(ch==34) // 34为双引号的ASCII值
break;
if(!ifstr)
return 0;
}
switch (ch)
{
case '{':
case '[':
case '(':
Push(a,ch); // 出现以上三种左括号则进栈
break;
case '}':
if(Peek(a)=='{')
Pop(a); // 栈顶的左花括号出栈
else
return 0;
break;
case ']':
if(Peek(a)=='[')
Pop(a); // 栈顶的左中括号出栈
else
return 0;
break;
case ')':
if(Peek(a)=='(')
Pop(a); // 栈顶的左圆括号出栈
else
return 0;
}
}
if(StackEmpty(a))
return 1;
else
return 0;
}
。收起
