数据结构-栈及栈的括号匹配

• 一、栈
• • 栈的定义
  • 基本操作
  • • 定义
    • 初始化
    • 入栈
    • 出栈
    • 测试函数
• 二、栈的应用-括号匹配
• • 匹配函数
  • 测试函数
• 三、完整代码

`

栈作为一种 数据结构 ，是一种只能在一端进行插入和删除操作的特殊 线性表 。. 它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。. 栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底 指针 。. 栈是允许在同一端进行插入和删除操作的特殊 线性表 。. 允许进行插入和删除操作的一端称为栈顶 (top)，另一端为栈底 (bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。. 插入一般称为 进栈 （push），删除则称为退栈（pop）。. 栈也称为先进后出表。

栈有顺序栈和链栈，在此，讨论顺序栈。顺序栈即栈的顺序储存结构，是利用一组地址连续的储存单元依次存放，并自栈底到栈顶的数据元素。由于栈在使用过程中所需要的大小难以估计，所以通常是先为栈分配一个基本容量，然后在使用过程中，当栈的空间不够使用时，再继续追加储存空间。

typedef struct CharStack
{
    int top;
    int data[STACK_MAX_SIZE];
}*CharStackPtr;

初始化为一个空栈。

CharStackPtr CharStackInit()
{
    CharStackPtr resPtr=(CharStackPtr)malloc(sizeof(struct CharStack));
    
    resPtr->top=-1;
    return resPtr;
}

void push(CharStackPtr pStackPtr,int pvalue)
{
    if(pStackPtr->top>=STACK_MAX_SIZE-1)
    {
        printf("无法进栈：栈已满!n");
        return;
    }
    
    pStackPtr->top++;
    pStackPtr->data[pStackPtr->top]=pvalue ;
}

char pop(CharStackPtr pStackPtr)
{
    if(pStackPtr->top<0)
    {
        printf("无法出栈：栈是空!n");
        return '';
    }
    
    pStackPtr->top --;
    return pStackPtr->data[pStackPtr->top+1];
    
}

void pushpopText()
{
	printf("-------------pushpopText bigins.------------n");
	CharStackPtr tempStack=CharStackInit();
	
	char ch;
	for(ch='a';ch<'m';ch++)
	{
		printf("Pushing %c n",ch);
		push(tempStack,ch);
		outputStack(tempStack);
	}
	int i;
	for(i=0;i<3;i++)
	{
		ch=pop(tempStack);
		printf("Pop %crn",ch);
		outputStack(tempStack);
	}
	printf("-------------pushpopText ends.------------n");
}

1、从头开始扫描字符串，如果是左括号，入栈；其他符号略过。
2、如果是右括号，检查栈是否为空，如果为空，说明没有左括号与当前的右括号相匹配。如果栈不为空且栈顶元素与当前符号相匹配，继续检查下一元素
3、重复以上过程，直至扫描完最后一个元素
4、检查栈是否为空，如果不为空，说明栈中还存有左括号没有与之对应的右括号相匹配，匹配失败。如果为空，说明匹配成功

bool brackeMatching(char* pString,int pLength)
{
//	printf("-------------brackeMatching bigins.------------n");
	CharStackPtr tempStack=CharStackInit();
	push(tempStack,'#');
	char tempchar,tempPopedchar;
	
	int i;
	for(i=0;i 
测试函数 
void brackeText()
{
	char* temp1="[3+(2*5)]*8";
	bool tempMacth1=brackeMatching(temp1,11);
	printf("rn");
	printf("该表达式 %s 匹配后的布尔值为:%d",temp1,tempMacth1);
	
	char* temp2="())";
	bool tempMacth2=brackeMatching(temp2,3);
	printf("rn");
	printf("该表达式 %s 匹配后的布尔值为:%d",temp2,tempMacth2);
	
	char* temp3="()()(())";
	bool tempMacth3=brackeMatching(temp3,8);
	printf("rn");
	printf("该表达式 %s 匹配后的布尔值为:%d",temp3,tempMacth3);
	
	char* temp4="({}[])";
	bool tempMacth4=brackeMatching(temp4,6);
	printf("rn");
	printf("该表达式 %s 匹配后的布尔值为:%d",temp4,tempMacth4);
	
	char* temp5=")(";
	bool tempMacth5=brackeMatching(temp5,2);
	printf("rn");
	printf("该表达式 %s 匹配后的布尔值为:%d",temp5,tempMacth5);
	
}
 
三、完整代码 
#include
#include
#include

#define STACK_MAX_SIZE 10

typedef struct CharStack
{
    int top;
    
    int data[STACK_MAX_SIZE];
}*CharStackPtr;

void outputStack(CharStackPtr pStack)
{
    int i;
    for(i=0;i<=pStack->top;i++)
    {
        printf("%c ",pStack->data[i]);
    }
    printf("n");
}

CharStackPtr CharStackInit()
{
    CharStackPtr resPtr=(CharStackPtr)malloc(sizeof(struct CharStack));
    
    resPtr->top=-1;
    return resPtr;
}

void push(CharStackPtr pStackPtr,int pvalue)
{
    if(pStackPtr->top>=STACK_MAX_SIZE-1)
    {
        printf("无法进栈：栈已满!n");
        return;
    }
    
    pStackPtr->top++;
    pStackPtr->data[pStackPtr->top]=pvalue ;
}

char pop(CharStackPtr pStackPtr)
{
    if(pStackPtr->top<0)
    {
        printf("无法出栈：栈是空!n");
        return '';
    }
    
    pStackPtr->top --;
    return pStackPtr->data[pStackPtr->top+1];
    
}

void pushpopText()
{
	printf("-------------pushpopText bigins.------------n");
	CharStackPtr tempStack=CharStackInit();
	
	char ch;
	for(ch='a';ch<'m';ch++)
	{
		printf("Pushing %c n",ch);
		push(tempStack,ch);
		outputStack(tempStack);
	}
	int i;
	for(i=0;i<3;i++)
	{
		ch=pop(tempStack);
		printf("Pop %crn",ch);
		outputStack(tempStack);
	}
	printf("-------------pushpopText ends.------------n");
}

bool brackeMatching(char* pString,int pLength)
{
//	printf("-------------brackeMatching bigins.------------n");
	CharStackPtr tempStack=CharStackInit();
	push(tempStack,'#');
	char tempchar,tempPopedchar;
	
	int i;
	for(i=0;i 
运行结果：
 
-------------pushpopText bigins.------------
Pushing a
a
Pushing b
a b
Pushing c
a b c
Pushing d
a b c d
Pushing e
a b c d e
Pushing f
a b c d e f
Pushing g
a b c d e f g
Pushing h
a b c d e f g h
Pushing i
a b c d e f g h i
Pushing j
a b c d e f g h i j
Pushing k
无法进栈：栈已满!
a b c d e f g h i j
Pushing l
无法进栈：栈已满!
a b c d e f g h i j
Pop j
a b c d e f g h i
Pop i
a b c d e f g h
Pop h
a b c d e f g
-------------pushpopText ends.------------

该表达式 [3+(2*5)]*8 匹配后的布尔值为:1
该表达式 ()) 匹配后的布尔值为:0
该表达式 ()()(()) 匹配后的布尔值为:1
该表达式 ({}[]) 匹配后的布尔值为:0
该表达式 )( 匹配后的布尔值为:0