欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构:栈的应用实现

程序员文章站 2024-01-24 17:12:34
...

题目:

假设一个字符串中可以包含三种括号:( )[ ]{},且这三种括号可以按任意次序嵌套使用(如:“…[…{…}…[…]…]…(…)” 为合法嵌套,“…[…{… )…[…]…]…(…)”为不合法嵌套)。编写判别给定表达式中所含括号是否正确配对出现的算法,如果是合法嵌套则返回为true,如果是不符合法嵌套则返回为false。

思路:

建立栈,有入栈,出栈,获取栈顶元素的功能,然后如果捕获数据为{ ,[,(则入栈,如果数据为),],}则获取栈顶元素,看是否相互匹配,如果不匹配则返回不合法,否则继续匹配,最终若栈空且最后一个元素匹配成功则合法

代码块:

#include "pch.h"
#include <iostream>
#include<string>
using namespace std;
struct stack
{
	char data;
	stack*next;
};
void init(stack *&s)//初始化栈
{
	s = NULL;
}
void push(stack *&s,char data)//前插法压入数据
{
	stack*tmp = new stack;
	tmp->data = data;
	tmp->next = s;
	s = tmp;
}
void pop(stack *&s)//弹出栈顶数据
{
	if (s == NULL) cout << "栈空" << endl;
	stack*tmp = s;
	s = s->next;
	delete tmp;
}
char top(stack *&s)//获取栈顶元素
{
	if (s == NULL)  return '#'; 
	return s->data;
}
bool match(stack *&s,char data)//配对函数
{
	cout << "输入元素为:" << data << endl;
	if (data == '(' || data == '{' || data == '[') push(s, data);
	else if (data == ')'&&top(s) != '(') { cout << "配对失败"; return false; }//如果匹配不成功返回错误
	else if (data == '}'&&top(s) != '{') { cout << "配对失败"; return false; }
	else if (data == ']'&&top(s) != '[') { cout << "配对失败"; return false; }
	else if (data == ')'&&top(s) == '(') { cout << "配对成功" << endl; pop(s); }//匹配成功则弹出栈顶元素,继续匹配
	else if (data == '}'&&top(s) == '{') { cout << "配对成功" << endl; pop(s); }
	else if (data == ']'&&top(s) == '[') { cout << "配对成功" << endl; pop(s); }
	return true;
}
bool main()
{
	while (true)
	{
		string test;//测试数据
		bool judge = false;
		cout << "请输入测试字符串:";
		cin >> test;
		cout << "测试用例为:" << test << endl;
		stack *s;
		init(s);
		for (auto c : test)//遍历测试数据,逐一匹配
		{
			if (c != '(' && c != '{' && c != '[' && c != ')'&& c != '}' && c != ']') { cout << "测试用例错误,请重新输入!"; break; }//若非要求字符,则退出
			judge = match(s, c);//判断是否匹配成功
			if (judge == false) break;//如果错误,直接退出
		}
		if (s != NULL) judge = false;//匹配成功最后栈顶应为空,否则,则有剩余符号,属于匹配失败
		if (judge) cout << "最终匹配成功\n";
		else cout << "最终匹配失败\n";
	}
}

效果图展示:
数据结构:栈的应用实现

相关标签: c++