数据结构之栈的括号匹配问题

问题描述

任意给定一个字符串，字符串中包含除了空格、换行符之外的任意字符。检测字符串中的各类括号是否配对，即“(”与“)”、“［”与“］”、“｛”与“｝”是否匹配。若匹配输出对应的匹配个数。

输入描述

一行字符串。

输出描述

如果字符串中的括号匹配，则输出数字 1，并且在下一行输出｛｝、［］、（）相对应的匹配个数，否则输出数字 0。

示例

输入：

&()dgn*[{%}12]

输出：

3

输入：

12(%]{

输出：

解题思路

这道题目在很多考研试卷中出过，或者是算法题，或者是简答题。遍历字符串，遇到左括号进栈，遇到右括号则判断是否与栈顶的左括号相匹配，匹配则栈顶元素出栈，否则跳过。

相关代码

本题目直接使用C++中的栈（ s t a c k stack stack）类来解答，省去了 p o p pop pop和 p u s h push push等函数的自定义。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<string>
#include <stack>
using namespace std;

int IsBracketMatching(string str)
{
	stack<char> s;
	int num = 0;
	for (int i = 0; i < str.size(); i++)// &()dgn*[{%}12]
	{
		if (str[i] == '(' || str[i] == '{' || str[i] == '[')
		{
			s.push(str[i]);
			continue;
		}
		if ((str[i] == ')' && s.top() == '(') || (str[i] == '}' && s.top() == '{') || (str[i] == ']' && s.top() == '['))
		{
			num++;
			s.pop();
		}
	}
	return num;
}

void main()
{
	string str;
	cout << "请输入一行字符串，可包含[,{,(,),},]等字符" << endl;
	cin >> str; // &()dgn*[{%}12]
	int num = 0;
	num = IsBracketMatching(str);
	cout << num << endl;
	system("pause");
	return;
}
           

运行结果

1、

请输入一行字符串，可包含[,{,(,),},]等字符

s(f[[{dfs}df]df]23)df

4

请按任意键继续. . .

2、

请输入一行字符串，可包含[,{,(,),},]等字符

&()dgn*[{%}12]

3

请按任意键继续. . .