信息学奥赛一本通 1355：字符串匹配问题(strs)

【题目链接】

ybt 1355：字符串匹配问题(strs)

【题目考点】

1. 栈

【解题思路】

设数组pri，pri[括号字符]是个整数表示括号的优先级。优先级从高到低为：<([{ ，
这里设pri[右括号] = 10*pri[左括号]，同类的左右括号的优先级数值是10倍关系，这样就可以用pri来判断两个括号是否配对。
遍历整个字符串

• 如果遇到左括号：只有栈空或当前左括号优先级大于等于栈顶左括号优先级时，左括号入栈。否则左括号优先级混乱，不匹配。
• 如果遇到右括号：如果栈空，则不匹配。如果栈不空，看栈顶左括号能否与该右括号配对，如果可以则出栈，否则不匹配。

结束遍历字符串后，看栈是否为空，如果不为空，则不匹配。

【题解代码】

解法1：

#include<bits/stdc++.h>
using namespace std;
int pri[128];//括号优先级 小括号优先级高，大括号优先级低。pri[右括号] = 10*pri[左括号]
void init()
{
    
    pri['{'] = 1;
	pri['['] = 2;
	pri['('] = 3;
	pri['<'] = 4;
	pri['}'] = 10;
	pri[']'] = 20;
	pri[')'] = 30;
	pri['>'] = 40;
}
int main()
{
    
	init();
	bool isMatch;
    int n;
	string s;
	stack<char> stk;
	cin >> n;
	while(n--){
    
		isMatch = true;
		stk = stack<char>();//清空栈 
		cin >> s;
		for(int i = 0; i < s.length(); ++i){
    
			if(stk.empty() || pri[s[i]] <= 4 && pri[s[i]] >= pri[stk.top()])//如果栈空或要入栈的左括号优先级更高 
				stk.push(s[i]);//入栈 
			else if(pri[s[i]] == 10*pri[stk.top()])//左括号优先级乘10等于右括号，即左右括号配对 
				stk.pop();//出栈 
			else//左右括号不匹配 或 栈空 
            {
    
				isMatch = false;
				break;
			}
		}
		if(stk.empty() == false)
            isMatch = false;
		if(isMatch)
			cout << "YES" << endl;
		else 
			cout << "NO" << endl;
	}
	return 0;
}