数据结构实验（括号配对问题）

一、 实验题目

设计算法判断一个算数表达式的圆括号是否正确配对。

二、问题分析

这道题用到的是栈的知识，这个程序要求我们知道如何对一个字符串进行存储，判断算数表达式是否配对正确的关键是对表达式进行扫描，熟悉圆括号的进出栈操作。

三、概要设计

1)为了实现上述程序功能，需要：[1]建立一个顺序栈；[2]键盘输入一个表达式，并对其进行扫描；[3]当扫描到“（”就进行入栈操作，遇到“）”就将栈顶元素出栈，扫描到其他元素不进行任何操作；[4]扫描完表达式，判断栈是否为空。若为空，则匹配正确，反之错误。 2)本程序包含的函数： [1]主函数main() [2]void Bracket()

四、详细设计

1)定义顺序栈类型 Typedefstruct{

Char stack[StackMaxSize]; Int top; }Stack;

2） [1]首先将定义一个栈S置成空栈，InitStack(S)；

[2]然后在main()里定义字符串str[100],并将其输入gets(str)； [3]接着利用while（str[i]!=’\\0’）语句对字符串进行扫描 [4]如果遇到“（“就执行push(S,’(‘)操作，遇到”)“就进行删除栈顶元素操作；

[5]最后判断栈是否为空，StackEmpty(S)。

五、调试分析

在一开始的试验中，在判断括号是否判断正确的if语句中if(!flag1&&flag2),这样得到的结果就不正确了，如图：

解决方法：将判断括号配对是否正确的if语句中if(!flag1&&flag2)改为if（！flag2）这样只要判断flag2标志的栈是否为空，从而得到括号是否配对正确。

六、测试结果：

1）测试数据：4+（4+5），））（（，）+（），）+（）+（ 2）测试结果截图：

七、附录（源代码）