文档介绍：河南工程学院《数据结构与算法》课程设计
成果报告
括号匹配算法设计的实现
题 目
括号匹配算法设计的实现
考核项目
考核内容
得分
平时考核题目设计选择的数据结构为栈。因为栈的特点是先进后出，使用栈使括号匹配问题简易化。多项式中的括号对数是成对出现的，可以将它抽象为一个对称的字符串，字符串的前一半看做连续出现的左括号字符，后一半看做连续出现的右括号字符，与栈顶元素比较，若匹配则栈顶指针下移，即删除栈顶元素，继续比较。当栈内元素为空时，说明左右的左括号与右括号匹配，则匹配成功。
算法描述
括号匹配问题是指要匹配一个字符串的左，右括号。括号问题可以用来解决C语言中的“{”和“}”的匹配问题，可以观察到，如果从左至右扫描一个字符串，那么每个右括号将于最近遇到的那个未匹配的左括号相匹配，在从左至右的扫描工程中把所遇到的左括号存放到堆栈内，每当遇到一个右括号时，就将它与栈顶的左括号（如果存在）相匹配，同时从栈顶删除该左括号。即假设一个算术表达式可以包含3种括号：圆括号“（”和“）”，方括号“[”“]”，和花括号“{”和“}”且这三种括号可按照任意次序嵌套使用（如：„[„{„}„[„]„]„[„]„（„）„）。设计一个程序，判别所给定表达式中所含括号是否匹配。在任意个表达式中，判断括号类型及其对数是否匹配。可以将表达式看做一个字符串，当此字符串为左括号时，将其入栈，当此字符串为右括号时，与栈顶元素比较，若不匹配则显示失败，若匹配，循环比较个字符与栈内元素是否匹配，直到栈为空且括号对数及类型相同，则该表达式的括号匹配，否则匹配失败。
程序流程图
4
。对括号出现的情况进行判断，如果是{、[、（则元素进栈，如果是}、]、）则与出栈元素进行比较。继续匹配，直到读完。若不匹配则进行标示，最后输出结果。
开始
输入字符串串
否
字符串没结束，匹配标示
是
判断括号
(
[
{
}
]
)
与出栈元素比较
括号进栈
是
是否匹配
否
输出结果
返回1
结束
5
3 程序清单
#include""
#include<iostream>
#include<>
#include<>
using namespace std;
#define stacksize 100 //定义栈的空间大小
struct stack{ //定义栈的结构体
char strstack[stacksize];//定义栈的存储格式为字符型
int top; //定义栈的栈顶变量
};
void InitStack(stack &s){ //定义一个新栈s，初始化栈顶为-1
= -1;
}
char Push(stack &s, char a){ //入栈操作，将字符a入栈s
if( == stacksize - 1) //当栈顶为栈的空间大小-1，栈满
return 0;
++;//入栈操作一次，栈顶+1
[] = a;//此时，栈顶元素为字符a
return a;
}
char Pop(stack &s ){ //出栈操作
if( == -1) //当栈顶为-1时，栈空
return 0;
6
char a = [];//将栈顶元素赋予字符a，并返回字符a，完成出栈操作
--;
return a;
}
int Empty(stack &s,int re){ //定义判断栈是否为空的函数
if(==-1)
return 1; //栈为空时返回值为1
else
return