括号匹配用什么数据结构_数据结构与算法题库

堆栈应用括号匹配实验 数据结构 　　文章目录 　　1实验目的 　　2实验要求与先验知识 　　3实验步骤 　　4实现代码 　　解决以下问题： 　　问题概述 　　一个算术表达式中包括圆括号、方括号和花括号三种形式的括号 　　编程实现判别表达式中括号是否正确匹配的算法 　　先验知识 　　一、栈 　　• 是一种线性表； 　　• 限定在表尾进行插入或者删除操作。 　　• 插入操作被称为 进栈 ， 　　• 删除操作被称为 出栈 。 　　• 允许插入和删除的一端（表尾）也被称为 栈顶 （ 　　top ）， 　　• 另外一端（表头）也被称为 栈底 （ 　　bottom ）。 　　• 后进先出（ LIFO ） 　　• 后进栈的素肯定比之前进 　　栈的素先出栈 　　• 先进后出：先进栈的素肯 　　定在后进栈的素之后才能出栈 　　二、栈的实现 　　• 栈的存储结构有 2 种 　　• 顺序栈 　　顺序栈 　　• 顺序栈是栈的顺序储存结构 　　• 利用一组地址连续的存储单依次存放 　　自栈底到栈顶的数据素 　　• 指针 top 指向栈顶素在顺序栈中的 下一 　　个位置 　　• base 为栈底指针，指向栈底的位置 　　• 链式栈
　　




　　算法思路
　　不匹配的情况： 　　遇到一个右括号，栈内弹出的左括号与之不匹配，例如 此时的右括号是 ] 而栈内的左括号是 { 　　匹配到最后一个括号。栈内已经空了，说明此时多出来了括号 　　处理完所有括号，栈内非空 　　C语言代码 　　匹配代码实现代码 　　void IsBracketCorrect(char exp[], int n) { 　　SeqStack myStack;//定义顺序堆栈变量“mystack” 　　char c; 　　int count1,count2; 　　StackInitiate(&myStack);//初始化顺序堆栈 　　for (int i = 0; i < n;i++) 　　{ 　　if ((exp[i] == ‘(‘ )|| (exp[i] == ‘[‘) || (exp[i] == ‘{‘)) { 　　StackPush(&myStack, exp[i]);//入栈 　　count1++; 　　} 　　else if (exp[i] == ‘)’ && StackNotEmpty(myStack) && StackTop(myStack, &c) && c == ‘(‘) 　　{ 　　StackPop(&myStack, &c);//出栈 　　count2++; 　　} 　　else if (exp[i] == ‘)’ && StackNotEmpty(myStack) && StackTop(myStack, &c) && c != ‘(‘) 　　{ 　　printf(” 左右括号匹配次序不正确！ 　　”); 　　return; 　　} 　　else if (exp[i] == ‘]’ && StackNotEmpty(myStack) && StackTop(myStack, &c) && c == ‘[‘) 　　{ 　　StackPop(&myStack, &c);//出栈 　　} 　　else if (exp[i] == ‘]’ && StackNotEmpty(myStack) && StackTop(myStack, &c) && c != ‘[‘) 　　{ 　　printf(“左右括号匹配次序不正确！ 　　”); 　　return; 　　} 　　else if (exp[i] == ‘}’ && StackNotEmpty(myStack) && StackTop(myStack, &c) && c == ‘{‘) 　　{ 　　StackPop(&myStack, &c);//出栈 　　} 　　else if (exp[i] == ‘}’ && StackNotEmpty(myStack) && StackTop(myStack, &c) && c != ‘{‘) 　　{ 　　printf(“左右括号匹配次序不正确！ 　　”); 　　return; 　　} 　　else if (((exp[i] == ‘)’) || (exp[i] == ‘]’ )|| (exp[i] == ‘}’)) && !StackNotEmpty(myStack)) 　　{ 　　printf(“右括号多于左括号！ 　　”); 　　return; 　　} 　　else if (((exp[i] == ‘)’) || (exp[i] == ‘]’ )|| (exp[i] == ‘}’)) && !StackNotEmpty(myStack)) 　　{ 　　printf(” 左括号多于右括号！ 　　”); 　　return; 　　} 　　else 　　{ 　　printf(“0 左右括号匹配次序正确”); 　　} 　　} 　　#include<stdio.h> 　　#include<string.h> 　　#include <iostream> 　　#define MaxStackSize 100   //顺序栈的最大长度 　　typedef char DataType; 　　typedef struct { 　　DataType stack[MaxStackSize]; 　　int top; 　　}SeqStack;SeqStack* S; 　　//初始化顺序堆栈S 　　void StackInitiate(SeqStack* S) { 　　S->top = 0; 　　} 　　//飞空否 　　//判断顺序堆栈S是否空，非空则返回1，否则返回0 　　int StackNotEmpty(SeqStack S) { 　　if (S.top <= 0) 　　return 0; 　　else 　　return 1; 　　} 　　//入栈 　　//把数据素的值x存入顺序堆栈S中，入栈成功返回1，否则返回0 　　int StackPush(SeqStack* S, DataType x) { 　　if (S->top >= MaxStackSize) { 　　printf(“堆栈已满无法插入！ 　　”); 　　return 0; 　　} 　　else { 　　S->stack[S->top] = x; 　　S->top++; 　　return 1; 　　} 　　} 　　//出栈 　　//取出顺序堆栈S的栈顶数据素值由参数d带回，出栈成功返回1，否则返回0 　　int StackPop(SeqStack* S, DataType* d) { 　　if (S->top <= 0) { 　　printf(“堆栈已空，无数据素可出栈！ 　　”); 　　return 0; 　　} 　　else { 　　S->top–; 　　*d = S->stack[S->top]; 　　return 1; 　　} 　　} 　　//取栈顶数据素 　　//取顺序栈顶S的当前栈顶数据素值由参数d带回，成功返回1，否则返回0 　　int StackTop(SeqStack S, DataType* d) { 　　if (S.top <= 0) { 　　printf(“栈顶已空！”); 　　return 0; 　　} 　　else { 　　*d = S.stack[S.top – 1]; 　　return 1; 　　} 　　} 　　//判断有n个字符的字符串exp匹配是否正确 　　void IsBracketCorrect(char exp[], int n) { 　　SeqStack myStack;//定义顺序堆栈变量“mystack” 　　char c; 　　int count1,count2; 　　StackInitiate(&myStack);//初始化顺序堆栈 　　for (int i = 0; i < n;i++) 　　{ 　　if ((exp[i] == ‘(‘ )|| (exp[i] == ‘[‘) || (exp[i] == ‘{‘)) { 　　StackPush(&myStack, exp[i]);//入栈 　　count1++; 　　} 　　else if (exp[i] == ‘)’ && StackNotEmpty(myStack) && StackTop(myStack, &c) && c == ‘(‘) { 　　StackPop(&myStack, &c);//出栈 　　count2++; 　　} 　　else if (exp[i] == ‘)’ && StackNotEmpty(myStack) && StackTop(myStack, &c) && c != ‘(‘) { 　　printf(” 左右括号匹配次序不正确！ 　　”); 　　return; 　　} 　　else if (exp[i] == ‘]’ && StackNotEmpty(myStack) && StackTop(myStack, &c) && c == ‘[‘) { 　　StackPop(&myStack, &c);//出栈 　　} 　　else if (exp[i] == ‘]’ && StackNotEmpty(myStack) && StackTop(myStack, &c) && c != ‘[‘) { 　　printf(“左右括号匹配次序不正确！ 　　”); 　　return; 　　} 　　else if (exp[i] == ‘}’ && StackNotEmpty(myStack) && StackTop(myStack, &c) && c == ‘{‘) { 　　StackPop(&myStack, &c);//出栈 　　} 　　else if (exp[i] == ‘}’ && StackNotEmpty(myStack) && StackTop(myStack, &c) && c != ‘{‘) { 　　printf(“左右括号匹配次序不正确！ 　　”); 　　return; 　　} 　　else if (((exp[i] == ‘)’) || (exp[i] == ‘]’ )|| (exp[i] == ‘}’)) && !StackNotEmpty(myStack)) { 　　printf(“右括号多于左括号！ 　　”); 　　return; 　　} 　　else if (((exp[i] == ‘)’) || (exp[i] == ‘]’ )|| (exp[i] == ‘}’)) && !StackNotEmpty(myStack)) { 　　printf(” 左括号多于右括号！ 　　”); 　　return; 　　} 　　else 　　{ 　　printf(“0 左右括号匹配次序正确”); 　　} 　　} 　　if (StackNotEmpty(myStack)) 　　{ 　　printf(“-1 左右括号配对次序不正确 　　”);//-1左右括号配对次序不正确 　　} 　　else 　　{ 　　printf(“0 左右括号匹配正确！ 　　”); 　　} 　　} 　　using namespace std; 　　int main() 　　{ 　　int e,f,g,h; 　　char a[e]; 　　char b[f]; 　　char c[g]; 　　char d[h]; 　　int i; 　　printf(“请输入几行字符串？： 　　”); 　　scanf(“%c”,&i); 　　fflush(stdin);   //清除标准缓冲区 　　printf(” 　　请输入第一行字符串：”); 　　scanf(“%c”,&a); 　　fflush(stdin);   //清除标准缓冲区 　　e = strlen(a); 　　printf(“%d”,e); 　　IsBracketCorrect(a,e); 　　printf(” 　　请输入第二行字符串：”); 　　scanf(“%c”,&b); 　　fflush(stdin);   //清除标准缓冲区 　　f = strlen(b); 　　IsBracketCorrect(b,f); 　　printf(” 　　请输入第三行字符串：”); 　　scanf(“%c”,&c); 　　fflush(stdin);   //清除标准缓冲区 　　g = strlen(c); 　　IsBracketCorrect(c,g); 　　printf(” 　　请输入第四行字符串：”); 　　scanf(“%c”,&d); 　　fflush(stdin);   //清除标准缓冲区 　　h = strlen(d); 　　IsBracketCorrect(d,h); 　　return (0); 　　}