[数据结构与算法] 数据结构我好爱：栈的应用--括号匹配

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构我好爱：栈的应用--括号匹配 -> 正文阅读

[数据结构与算法]数据结构我好爱：栈的应用--括号匹配

我们可以通过栈来匹配括号是否齐全：把左括号压入栈，当遇见右括号且与栈顶括号匹配的时候，我们将栈顶的左括号弹出，继续检验。

简直就是用栈的完美特性“先进后出”

常规操作：压栈与入栈就不说了！

主要函数：括号匹配函数：

????????1.开始逐个遍历字符串

????????2.将左括号读入

????????3.如果有拥有右括号且与栈顶括号匹配，弹出栈顶，否则return 0；

????????4.防止最后一个元素为左括号压入了栈，检查栈顶是否为提前设置的#，否则return 0

? ? ? ? 5.最终return 1，括号匹配成功

int baketJudge(char* str) {
	stackPtr head = InitStack();
	push(head, '#');
	char topc;
	for (int i = 0; i < strlen(str); i++) {
		char tempc = str[i];

		switch (tempc) {
		case '(':
		case '[':
		case '{':
			push(head, tempc);
			break;
		case ')':
			topc = pop(head);
			if (topc != '(') return 0;
			break;
		case ']':
			topc = pop(head);
			if (topc != '[') return 0;
			break;
		case '}':
			topc = pop(head);
			if (topc != '{') return 0;
			break;
		default:
			break;
		}
	}
	topc = pop(head);
	if (topc != '#') {
		return 0;
	}
	return 1;
}

完整代码：

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

typedef struct {
	char data[20];
	int top;
}*stackPtr,stack;

void Print(stackPtr head) {
	if (head->top == -1) return;
	for (int i = head->top; i >= 0; i--) {
		printf("%c ", head->data[i]);
	}
}


stackPtr InitStack() {
	stackPtr head = (stackPtr)malloc(sizeof(stack));
	head->top = -1;
	return head;
}

void push(stackPtr head, char c) {
	if (head->top >= 18) {
		printf("no space");
		return;
	}
	head->top++;
	head->data[head->top] = c;
}

char pop(stackPtr head) {
	char tempchar = head->data[head->top];
	head->top--;
	return tempchar;
}

int baketJudge(char* str) {
	stackPtr head = InitStack();
	push(head, '#');
	char topc;
	for (int i = 0; i < strlen(str); i++) {
		char tempc = str[i];

		switch (tempc) {
		case '(':
		case '[':
		case '{':
			push(head, tempc);
			break;
		case ')':
			topc = pop(head);
			if (topc != '(') return 0;
			break;
		case ']':
			topc = pop(head);
			if (topc != '[') return 0;
			break;
		case '}':
			topc = pop(head);
			if (topc != '{') return 0;
			break;
		default:
			break;
		}
	}
	topc = pop(head);
	if (topc != '#') {
		return 1;
	}
	return 1;
}

void Test() {
	char* tempExpression = "[2 + (1 - 3)] * 4";
	printf("%s \n", tempExpression);
	if (baketJudge(tempExpression)) printf("true\n");
	else printf("false\n");

	char* tempExpression1 = "[2 + (1 - 3)]) * 4";
	printf("%s \n", tempExpression1);
	if (baketJudge(tempExpression1)) printf("true\n");
	else printf("false\n");
}

int main() {
	Test();
	return 0;
}