数据结构:栈的应用实现
程序员文章站
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";
}
}
效果图展示:
上一篇: 数据结构之栈和队列的实现
下一篇: BMP格式学习