数据结构（C语言）之——链栈

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef char ElemType; //定义元素类型

typedef struct LinkNode{
	ElemType elem; //数据域
	struct LinkNode *next; //指针域
}LinkNode;

typedef struct LinkStack{
	struct LinkNode* head; //头结点
	int length; //栈的当前结点个数
}LinkStack;

//创建一个空栈
LinkStack* createStack() {
	LinkStack* s = (LinkStack*) malloc(sizeof(LinkStack));
	s->head = (LinkNode*) malloc(sizeof(LinkNode));
	s->head->next = NULL;
	s->length = 0;
	return s;
}

//释放栈
void releaseStack(LinkStack* s) {
	LinkNode* p;
	while(s->head != NULL) {
		p = s->head;
		s->head = s->head->next;
		free(p);
	}
	free(s);
}

//判断栈空
bool isEmpty(LinkStack* s) {
	return (s == NULL || s->length == 0) ? true : false;
}

//入栈操作(头插)
bool push(LinkStack* s, ElemType e) {
	if(s == NULL) return false;
	LinkNode* node = (LinkNode*) malloc(sizeof(LinkNode));
	if(node == NULL) return false;
	node->elem = e;
	node->next = s->head->next;
	s->head->next = node;
	s->length += 1;
	return true;
}

//出栈操作（头删）
ElemType pop(LinkStack* s) {
	if(s == NULL || isEmpty(s)) return NULL;
	LinkNode* ptr = s->head->next;
	ElemType e = ptr->elem;
	s->head->next = s->head->next->next;
	free(ptr);
	s->length -= 1;
	return e;
}

//栈的应用：括号匹配
void bracketCheck() {
	printf("
/**********栈的应用：括号匹配***********/
");
	printf("输入表达式：");
	char str[100]; int length;
	scanf("%s", &str); length = strlen(str);

	bool flag = true;
	LinkStack* s = createStack();
	for(int i=0; i<length; i++) {
		if(str[i] == ( || str[i] == [ || str[i] == {) {
			push(s, str[i]); //扫描到左括号则入栈
		}else if(str[i] == ) || str[i] == ] || str[i] == }){
			if(isEmpty(s)) {
				flag=false; //扫描到右括号且当前栈空，则匹配失败
				break;
			}
			char topElem = pop(s);
			if(str[i] == ) && topElem != () {
				flag=false; break;
			}
			if(str[i] == ] && topElem != [) {
				flag=false; break;
			}
			if(str[i] == } && topElem != {) {
				flag=false; break;
			}
		}
	}
	if(flag == true && isEmpty(s)) {
		printf("括号匹配成功！
");
	}else {
		printf("括号匹配失败！
");
	}
	releaseStack(s);
}

int main() {
	LinkStack* s = createStack();
	printf("输入入栈序列（从左至右依次入栈）：（如abcdefg）：");
	char inputStr[100];
	scanf("%s", &inputStr);
	for(int i=0; i<strlen(inputStr); i++) {
		push(s, inputStr[i]);
	}
	ElemType e;
	printf("出栈序列（从左至右依次出栈）：");
	while(!isEmpty(s)) {
		e = pop(s);
		printf("%c", e);
	}
	printf("
");
	releaseStack(s);

	//栈的应用：括号匹配
	bracketCheck();

	return 0;
}

结果：

输入入栈序列（从左至右依次入栈）：（如abcdefg）：abcd
出栈序列（从左至右依次出栈）：dcba

/**********栈的应用：括号匹配***********/
输入表达式：{1+2*[5/(4+2)]}
括号匹配成功！