[C++知识库]深入浅出检查括号匹配性(栈)(C++)

1)检查括号匹配性

若有字符串为"({}<>)({})"则符合匹配性（一个正括一定有一个反括号，嵌套在括号中的括号也必须进行判断）

2)不符合匹配性的情况

“><(}{)["不符合匹配性（先出现反括号再出现正括号，或嵌套在正括号种存在不匹配的括号等）

3)思路

例如 "( { }?)"

第一个字符是 '(' ，所以压入栈，此时栈不为空。

第二个字符是 '{' ，所以再次压入栈。

第三个字符是 '}' ，栈不为空，所以弹出栈的第一个元素 '{'。

第四个字符是 ')' ，栈不为空，弹出栈里第一个元素 '('。

结束，栈为空，符合匹配性，return true

例如 "( < >"

第一个字符是 '('，所以压入栈，此时栈不为空。

第二个字符是 '<'，继续压入栈。

第三个字符是 '>'，栈不为空所以弹出 '<'。

结束，栈不为空，不符合匹配性，return false

4)源码

#include<iostream>
using namespace std;
#include<stack>

bool isbracket(string c)
{
	stack<char> s;
	for (int i = 0; i < c.length(); i++)
	{
		if (c[i] == '[' || c[i] == '(' || c[i] == '{' || c[i] == '<')
		{
			s.push(c[i]);
		}
		else if (c[i] == '}' || c[i] == ']' || c[i] == '>' || c[i] == ')')
		{
			if (s.empty())
				return false;
			else
				s.pop();
		}
	}
	if (c.empty())
		return true;
	else
		return false;
}

int main()
{
	string s1 = "({}<>)";
	string p = isbracket(s1) ? "yes" : "no";
	cout << p << endl;
	string s2 = "()}{";
	p = isbracket(s2) ? "yes" : "no";
	cout << p << endl;
}