数据结构 C 代码6：栈以及括号匹配

栈 是一个线性表，插入和删除位置限制在线性表的尾部进行要插入X，只能插入在最后一个元素的后面，也只能删除最后一个元素

栈是插入和删除受到限制的线性表

通常将允许删除，插入操作的一端称为栈顶，另一端称为栈底

不含任何一个元素的栈称为空栈

栈是一种先进后出(Last IN First Out)的线性表，简称LIFO
栈的插入操作被形象的称为进栈，或入栈(压栈)
删除操作被称为出栈，或退栈(弹出)

1.栈的结构定义

typedef struct CharStack {
    int top;

    int data[STACK_MAX_SIZE];
} *CharStackPtr; 

2.输出数据

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

3.打印

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

4.入栈

void push(CharStackPtr paraStackPtr, int paraValue){
	if(paraStackPtr->top>=STACK_MAX_SIZE-1){
		printf("can't push , Stack is full.nr");
		return;
	}
	paraStackPtr->top++;
	paraStackPtr->data[paraStackPtr->top]=paraValue;
}

5.出栈

char pop(CharStackPtr paraStackPtr){
	if(paraStackPtr->top<0){
		printf("can't pop , Stack is empty.rn");
		return '';
	}
	paraStackPtr->top--;
	return paraStackPtr->data[paraStackPtr->top+1];
}

6.测试

void pushPopTest(){
	printf("----pushPopTest begins.----rn");
	
	
	CharStackPtr tempStack = charStackInit();
	printf("After initialization,the stack is: ");
	outputStack(tempStack);
	
	
	for(char ch = 'a'; ch < 'm';ch ++){
		printf("Pushing %c.rn",ch);
		push(tempStack,ch);
		outputStack(tempStack);
	}
	
	
	for(int i = 0;i < 3;i ++){
		ch = pop(tempStack);
		printf("Pop %c.rn",ch);
		outputStack(tempStack);
	}
	
	printf("---pushPopTest ends.---rn");
}

7.测试结果

---- pushPopTest begins. ----
After initialization, the stack is:
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.
Cannot push element: stack full.
a b c d e f g h i j
Pushing l.
Cannot push element: stack full.
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
---- pushPopTest ends. ----
Press any key to continue

栈结构具有后进先出的特点。括号匹配问题描述：若表达式中包含三种括号：圆括号、方括号和花括号，它们可以相互嵌套。

算法思想：检验算法中可设置一个栈，每读入一个括号，若是左括号，则直接进栈，等待相匹配的同类右括号；若读入的是右括号，且与当前栈顶左括号同类型，则二者匹配，将栈顶的左括号弹出，否则属于不合法情况。另外。如果输入序列已经读完，而栈中仍有等待匹配的左括号，或者读入一个右括号，而栈中已无等待匹配的同类型左括号，均属于不合法情况。当输入序列和栈同时变空的时候，说明所有括号完全匹配。

1.栈的应用

bool bracketMatching(char* paraString, int paraLength){
	char tempChar, tempPopedChar;
	CharStackPtr tempStack=charStackInit();
	push (tempStack,'#');
	for(int i=0;i 
2.代码测试
 
void bracketMatchingTest() {
	char* tempExpression = "[2 + (1 - 3)] * 4";
	bool tempMatch = bracketMatching(tempExpression, 17);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);


	tempExpression = "( )  )";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);

	tempExpression = "()()(())";
	tempMatch = bracketMatching(tempExpression, 8);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);

	tempExpression = "({}[])";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);


	tempExpression = ")(";
	tempMatch = bracketMatching(tempExpression, 2);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);
}
 
3.测试结果
 
Is the expression '[2 + (1 - 3)] * 4' bracket matching? 1
Is the expression '( )  )' bracket matching? 0
Is the expression '()()(())' bracket matching? 1
Is the expression '({}[])' bracket matching? 1
Is the expression ')(' bracket matching? 0
Press any key to continue