数据结构括号匹配算法

※数据结构综合实验报告

实验一括号的匹配问题

一．实验目的：

（1）熟练掌握数据结构的基本知识。

（2）掌握线性结构中队列设计的基本思路、应用方法，以及存储于队列中数据之间的逻辑关系与性质。

（3）能够利用所学的基本知识和技能，解决简单的数据结构算法设计与分析。

二．实验环境及软件

操作系统：Windows XP，开发工具：VC++6.0

三．实验内容：

1.问题描述（功能要求）：

一个表达式中包括变量、常量、操作符、圆括号，圆括号可以嵌套, 编写程序判断表达式中的括号是否正确匹配。输入任意一个表达式，判断其中括号是否匹配，匹配, 输出OK, 不匹配，输出NO。(表达式的长度小于50)

四．具体算法设计详解：

1.创建一个空栈b,数据类型为字符型。

2.输入一个字符型数组a。

3.逐字符扫描输入的字符串a。

2.1 假如是‘(’则调用Push(x)函数，将其压入栈。

2.2 假如是‘)’,则将该值赋给同样是字符型的数组c，并令计

数器i+1，继续检测输入字符串的下一个字符。

4.假如输入字符串的字符都扫描完了。调用计数器i次的Pop（）函数，每次调用另一个计数器k+1。当栈b为空时，停止调用函数Pop()。

5.比较计数器i和k的值。如果相等，则呈现匹配，输出OK。如过i与k不等，则呈现不匹配，输出NO。

五．具体代码实现详细分析：

1.先定义一个存储点信息的结构体Node

struct Node

{

T data;

Node *next;

};

2.再定义一个存储栈的数据及具体操作的类linkStack

class linkStack

{

public:

linkStack(){top=NULL;length=0;} //栈的构造函数

~linkStack(); //栈的析构函数

void Push(T x); //入栈函数

int Pop(); //出栈函数

int Empty(){if(top==NULL)return 0;else return 1;} //判断栈是否为空private:

Node *top; //结点top

int length; //栈的长度

};

3.各函数的分析

(1)数据入栈

void linkStack::Push(T x)

{

Node *s; //定义一个节点

if(length>=50)cout<<"上溢"<

else

{

s=new Node;s->data=x; //新建结点，并使其入栈，栈的长度length++ s->next=top;top=s;

length++;

}

}

（2）数据出栈

int linkStack::Pop()

{

Node*q; //定义一个暂存结点

if(top==NULL)return 0; //栈空，返回0

else

{ //反之，将栈顶元素出栈，栈长度length-1， q=top; //并返回值1

top=top->next;

delete q;

length--;

return 1;

}

}

（3）主函数的设计

int main()

{

char a[50],c[50]; //定义两个长度为50的字符型数组 linkStack b; //定义一个空栈b,类型为字符型

int n,i=0,k=0; //定义两个计数器i和k，并初始为0 scanf("%s",a); //输入一个字符串

for(n=0;n<50;n++)

{

if(a[n]=='(')b.Push(a[n]); //如果是‘（’则入栈

else if(a[n]==')') //如果是‘）’则赋给数组c,计数器i++

{

c[i]=a[n];

i++;

}

}

for(n=0;n<=i;n++) //如果栈不为空，使栈中元素出栈，并且计数器k++ {

if(b.Pop()==1)k++;

else

break;

}

if(k==i)cout<<"OK"<

else cout<<"NO"<

}

六．实验结果（接实验结果截屏）：

a.表达式括号不匹配

b.表达式括号匹配成功

七．附实验代码：

#include

#include

using namespace std;

template

struct Node

{

T data;

Node *next;

};

template

class linkStack

{

public:

linkStack(){top=NULL;length=0;}

~linkStack();

void Push(T x);

int Pop();

int Empty(){if(top==NULL)return 0;else return 1;}

Node *top;

int length;

};

template

void linkStack::Push(T x)

{

Node *s;

if(length>=50)cout<<"上溢"<

else

{

s=new Node;s->data=x;

s->next=top;top=s;

length++;

}

}

template

int linkStack::Pop()

{

Node*q;

if(top==NULL)return 0;

else

{

q=top;

top=top->next;

delete q;

length--;

return 1;

}

}

template

linkStack::~linkStack()

{

Node *p;

while(top)

{

p=top;

top=top->next;

delete p;

length--;

}

int main()

{

char a[50],c[50];

linkStack b;

int n,i=0,k=0;

scanf("%s",a);

for(n=0;n<50;n++)

{

if(a[n]=='(')b.Push(a[n]);

else if(a[n]==')')

{

c[i]=a[n];

i++;

}

}

for(n=0;n<=i;n++)

{

if(b.Pop()==1)k++;

else

break;

}

if(k==i)cout<<"OK"<

}