一、问题描述

设计一个算法判断表达式中的括号是否匹配

二、问题解答

解析:这里需要用到STL在算法设计中的应用,STL在算法设计中的应用有如下几种:
Ⅰ.存放主数据
⭐ Ⅱ.存放临时数据
Ⅲ.检测数据元素的唯一性
Ⅳ.数据的排序
Ⅴ.优先队列作为堆
因此这里需要用上的就是Ⅱ.存放临时数据
这里的主数据是一个字符串表达式,采用string字符串str存储它。在判断括号是否匹配时需要用到栈(因为每个右括号都是与前面最近的左括号匹配),采用stack<char>容器作为栈。
对应程序如下:

#include<iostream>
#include<string>
#include<stack>
using namespace std;
bool solve(string str)
{
	stack<char> st;
	int i=0;
	while(i<str.length()){//判断str中的括号是否匹配 
		if(str[i]=='('||str[i]=='['||str[i]=='{')
			st.push(str[i]);
		else if(str[i]==')')
		{
			if(st.top()=='(') 
				st.pop();
			 else return false;
		}
		else if(str[i]==']')
		{
			if(st.top()=='[') 
				st.pop();
			 else return false;
		}
		else if(str[i]=='}')
		{
			if(st.top()=='{') 
				st.pop();
			 else return false;
		}
		i++;
	}
	if(st.empty())
	return true;
	else return false;
}
int main(){
	string str="(a+[b-c]+d)";
	cout<<" "<<str<<(solve(str)?"括号匹配":"括号不匹配")<<endl;
	str="(a+[b-c]+d}";
	cout<<" "<<str<<(solve(str)?"括号匹配":"括号不匹配")<<endl;
	return 0;
}  

`

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐