堆栈应用括号匹配实验

深圳大学实验报告

课程名称：数据结构实验与课程设计

实验项目名称：堆栈应用括号匹配实验

学院：计算机与软件学院

专业：未分

指导教师：杨芳

报告人：姜家祥学号：2013150387 班级：08

实验时间：2013-10-9

实验报告提交时间：2014-10-10

教务处制

一、实验目的

掌握堆栈的基本原理

掌握堆栈的存储结构

掌握堆栈的进栈、弹栈、判断栈空的实现方法

掌握应用堆栈实现括号匹配的原理和实现方法

二、实验要求

熟悉C++语言编程

熟练使用C++语言实现堆栈的进栈Push、插入Pop、判断栈空等操作

熟练使用堆栈实现括号匹配算法

三、实验内容

本次实验有两项内容：

（一）堆栈应用括号匹配

1、问题描述

一个算术表达式中包括圆括号、方括号和花括号三种形式的括号

编程实现判别表达式中括号是否正确匹配的算法

2、算法

顺序扫描算术表达式

若算术表达式扫描完成，此时如果栈空，则正确返回(0)；如果栈未空，说明左括号多于右括号，返回(-3)

从算术表达式中取出一个字符，如果是左括号(‘(‘或‘[‘或‘{‘)，则让该括号进栈(PUSH)

如果是右括号(‘)‘或‘]‘或‘}‘)：

⑵ 、如果栈为空，则说明右括号多于左括号，返回(-2)

⑵、如果栈不为空，则从栈顶弹出(POP)一个括号：若括号匹配，则转1继续进行判断；否则，说明左右括号配对次序不正确，返回(-1)

3、输入

第一行：样本个数，假设为n。

第二到n+1行，每一行是一个样本（算术表达式串），共n个测试样本。

4、输入样本

4

{[(1+2)*3]-1}

{[(1+2]*3)-1}

(1+2)*3)-1}

{[(1+2)*3-1]

5、输出

共有n行，每一行是一个测试结果，有四种结果：

0：左右括号匹配正确{[(1+2)*3]-1}

-1：左右括号配对次序不正确{[(1+2]*3)-1}

-2：右括号多于左括号(1+2)*3)-1}

-3：左括号多于右括号{[(1+2)*3-1]

6、输出样本

-1

-2

-3

（二）数制转换

1、问题描述

对于任意十进制数转换为k进制，包括整数部分和小数部分转换。整数部分采用除k求余法，小数部分采用乘k取整法例如x=19.125，求2进制转换

整数部分19，小数部分0.125

19 / 2 = 9 ... 10.125 * 2 = 0.25 0

9 / 2 = 4 ... 10.25 * 2 = 0.5 0

4 / 2 = 2 ... 0 0.5 * 2 = 1 (1)

2 / 2 = 1 0

1 / 2 = 0 (1)

所以整数部分转为 10011，小数部分转为0.001，合起来为10011.001

提示整数部分可用堆栈，小数部分可用队列实现

注意：必须按照上述方法来实现数制转换，其他方法0分

2、输入

第一行输入一个t，表示下面将有t组测试数据。

接下来每行包含两个参数n和k，n表示要转换的数值，可能是非整数；k表示要转换的数制，1

3、输出

对于每一组测试数据，每行输出转换后的结果，结果精度到小数点后3位

4、输入样本

2

19.125 2

15.125 16

5、输出样本

10011.001

F.200

四、程序清单

#include

using namespace std;

#include

#define Max_Size 100

typedef struct Stack{ //定义栈char base[Max_Size];

int top;

}Stack;

void InitStack(Stack &S){ //构造空栈S.top=0;

}

int Push(Stack &S,char ch){ //元素进栈S.top++;

S.base[S.top]=ch;

return 1;

}

int Pop(Stack &S,char ch){ //元素出栈S.top--;

ch=S.base[S.top];

return 1;

}

int Empty(Stack &s,int n){

if(s.top==0){

return 1;}

else{

return 0;}}

int Pipei(Stack &S,string S1){ //匹配

int i,m=0,n=0,num=0,num1=0; char c,ch,ch1,ch2[100];

InitStack(S);

for(i=0;i

c=S1[i];

if(c=='('||c==')'||c=='{'||c=='}'||c=='['||c==']')

ch2[m++]=c;

}

//把字符组S1的括号复制到ch2中

for(i=0;i<=m-1;i++){

ch=ch2[i];

if(ch=='('||ch=='{'||ch=='[')

Push(S,ch);//左括号，进栈

if(ch==')'||ch=='}'||ch==']'){

num1++;

if((ch==')'&&S.base[S.top]=='(')||(ch=='}'&&S.base[S.top]=='{')||(ch==']'&&S.base[S.top]== '['))

Pop(S,ch1);//右括号匹配栈顶左括号，左括号出栈

else{

i=m-1;

return -1;

}//左右括号不匹配

if(Empty(S,n)&&i

return -2;//右括号多于左括号