ZJNU 数据结构1002 实验二 括号匹配判断算法 栈的运用

Description

假设在表达式中([]())或[([ ][ ])]等为正确的格式,[( ])或([( ))或 (( )])均为不正确的格式。基于栈设计一个判断括号是否正确匹配的算法。

Input

输入数据有多组,每组测试数据一行,一个字符串(长度小于1000),只包含 ‘[‘ ,’]’ ,’(‘ ,‘)’ 。

Output

对于每组测试数据,若括号匹配输出yes,否则输出 no。

Sample Input

[]()[]

([[]])[)

Sample Output

yes

no

 

嘿嘿,本题没有使用栈的头文件,一切函数都是需要自己定义的

代码区:

#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <iostream>
using namespace std;
typedef struct stack //定义一个结构体为栈(注意,本题没有使用栈的头文件,一切函数都是自己定义的)
{
	char ch[1000];//存放括号
	int top;//栈顶指针(所指的那位置是空的,是栈顶元素的上面)
	int base;//栈底指针(指向栈底元素的下面)
}*ST,Stack;//前者为栈指针,后者为栈结构体

ST InitStack()//创建一个栈
{
	ST st;
	st=(ST)malloc(sizeof(Stack));//开辟空间
	st->top=0;//将栈顶指针和栈底指针初始化
	st->base=0;
	return st;//返回栈的地址
}

int Pop(ST st)//弹出函数,作用是将栈顶元素弹出
{
	st->top--;//先让指针向下获得栈顶元素的地址
	return st->ch[st->top];//返回栈顶元素
}

void Push(ST st,char c)//推入函数,作用是将元素推入栈顶
{
	st->ch[st->top]=c;//推入栈顶
	st->top++;//栈顶指针++
}

void check(ST st,string a)//判断函数
{
	int i,t;
	Push(st,a[0]);//将空白元素推入栈,是因为需要使栈底指针指向空,从下标1开始
	for (i=1;i<a.size();i++)//a.size()是指a字符串的长度
	{
		if ((a[i]==']'&&st->ch[st->top-1]=='[')||(a[i]==')'&&st->ch[st->top-1]=='('))
            //依次对比字符串中的括号,如果和栈顶的括号匹配的话说明这个括号可以抵消了
            //须知,因为栈的性质是先入后出,所以字符串从前往后,栈从后往前,完美!
			t=Pop(st);//所以需要弹出栈
		else
			Push(st,a[i]);//如果该字符串元素不能完成括号匹配,就先暂时压入栈中(地牢)等待另一半括号来救
	}
	if(st->top==0)//当栈顶指针指向0说明栈中已经没有元素了,也就表面括号已经全部匹配成功了
		cout << "yes" << endl;
	else//反之没有匹配成功
		cout << "no" << endl;
}

int main()
{
	string s;//定义字符串
	while(cin >> s)//多组测试数据
	{
		ST st;
		st=InitStack();//调用函数
		check(st,s);//调用函数
	}
    return 0;
}

新手上路,有错请指正

上一篇:HBase操作


下一篇:PTA乙级|1002 写出这个数