【Brackets Matching】带有等级顺序的括号匹配问题 ——C++实现

• 题目描述

• The input string contains only 4 types of brackets, (), [], <> and {}. The goal is to determine whether each sequence of brackets is matched. If the input string has multiple levels of enclosure, the order of brackets must be <>, (), [], {} from inside to outside.

• For example, if we input: [()], output should be ‘YES’, while input ([]) or [(], output should be ‘NO’.

• Input

• The first line of the input is an integer N, indicating how many strings below. The next N lines, each line is a string consisting of brackets and no longer than 255.

• Output

• There are N lines in the output, each line is either YES or NO.

样例输入输出
输入:
5
{}{}<><>()()[][]
{{}}{{}}<<>><<>>(())(())[[]][[]]
{{}}{{}}<<>><<>>(())(())[[]][[]]
{<>}{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]
<}{{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]
输出:
YES
YES
YES
YES
NO

示例代码：

//Brackets Matching
//                               2020.3.2
//                               J.York
#include<iostream>
#include<string>
#include<stack>
using namespace std;

int getrank(char c) {
	if (c == ‘<‘)
		return 1;
	if (c == ‘(‘)
		return 2;
	if (c == ‘[‘)
		return 3;
	if (c == ‘{‘)
		return 4;
	if (c == ‘>‘)
		return -1;
	if (c == ‘)‘)
		return -2;
	if (c == ‘]‘)
		return -3;
	if (c == ‘}‘)
		return -4;
}

int main() {
	int n;
	string s;
	cin >> n;
	int* array1 = new int[n];
	for (int i = 0; i < n; i++)
	{
		stack<char>charstack;
		cin >> s;
		if (s.length() % 2 == 1)
		{
			array1[i] = 0;
			goto mark1;;
		}
		for (int k = 0; k < s.length(); k++)
		{
			if (charstack.empty()) {
				if (getrank(s[k]) > 0)
				{
					charstack.push(s[k]);
				}
				else
				{
					array1[i] = 0;
					goto mark1;;
				}
			}
			else {
				if (getrank(s[k]) > 0)
				{
					if (getrank(s[k]) <= getrank(charstack.top())) {
						charstack.push(s[k]);
					}
					else
					{
						array1[i] = 0;
						goto mark1;;
					}
				}
				else
				{
					if (charstack.empty())
					{
						array1[i] = 0;
						goto mark1;;
					}
					else
					{
						if (getrank(s[k]) == -getrank(charstack.top()))
						{
							charstack.pop();
						}
						else
						{
							array1[i] = 0;
							goto mark1;;
						}
					}
				}
			}

		}
		if (charstack.empty())
		{
			array1[i] = 1;
		}
		else
		{
			array1[i] = 0;
		}
	mark1:;
	}
	for (int i = 0; i < n; i++)
	{
		if (array1[i] == 0) {
			cout << "NO" << endl;
		}
		else {
			cout << "YES" << endl;
		}
	}
}