题解：括号的匹配_P1067

mzymzyo VIP

TA的个人主页 >

文章

粉丝

505

获赞

访问

370.4k

题解：括号的匹配

mzymzyo VIP

P1067 中山大学2019年机试题

发布于2020年3月12日 03:06

阅读数 9.9k

这道题很明显用栈来写。

遍历字符串，遇到左括号时，先和栈顶元素判断是否符合括号优先级，不符合直接GG。否则入栈。

遇到右括号时，看和栈顶的括号是否相匹配，是的话弹出栈顶元素，不是的话直接GG。

最后再判断一下栈内元素是否全部弹出,栈内还有括号未匹配，直接GG，否则合法。

此题就结束了。

还要稍微注意一下栈内为空的情况下无法弹出元素。

#include<bits/stdc++.h>
using namespace std;
int val[127];
int n;
int main()
{
	val['<'] = 1; val['('] = 2; val['['] = 3; val['{'] = 4;
	cin >> n;
	while (n--)
	{
		stack <char> S;
		string str;
		cin >> str;
		for (int i = 0; i < str.length(); i++)
		{
			if (str[i] == '<' || str[i] == '(' || str[i] == '[' || str[i] == '{')
			{
				if (!S.empty() && val[str[i]] > val[S.top()])
					goto GG;
				S.push(str[i]);
			}
			else
			{
				if (S.empty())
					goto GG;
				if (S.top() == '<' && str[i] == '>' ||
					S.top() == '(' && str[i] == ')' ||
					S.top() == '[' && str[i] == ']' ||
					S.top() == '{' && str[i] == '}')
					S.pop();
				else
					goto GG;
			}
		}
		if (!S....

登录查看完整内容

登录后发布评论

3 条评论

seottle

2020年3月15日 14:30

同学你好，我在你的代码上改进了，但是正确率60%，不知道错在哪里了，你可以看看吗

int Priotity(char ch){

if(ch == '{') return 4;

else if(ch == '[') return 3;

else if(ch == '(') return 2;

else if(ch == '<') return 1;

}

int main() {

int n;

scanf("%d", &n);

while(n--) {

bool flag = true;

stack<char> brackets;

string str;

cin >> str;

for(int i = 0; i < str.size(); ++i) {

if(str[i] == '{' || str[i] == '[' || str[i] == '(' || str[i] == '<') {

if(!brackets.empty() && Priotity(str[i]) > Priotity(brackets.top())) { //栈不为空，且此时的优先级比栈顶元素还高

printf("NO\n");

flag = false;

break;

}

else

{

brackets.push(str[i]);

}

else {

if(brackets.empty()) {

printf("NO\n");

flag = false;

break;

}

if(brackets.top() == '{' && str[i] == '}' ||

brackets.top() == '[' && str[i] == ']' ||

brackets.top() == '(' && str[i] == ')' ||

brackets.top() == '<' && str[i] == '>' ) brackets.pop();

else

{

printf("NO\n");

flag = false;

break;

}

if(flag == true) printf("YES\n");

}

return 0;

}

mzymzyo : 回复 seottle：看我代码第35行，你最后还要判断栈内是否为空，比如说“（（<>）”虽然每个右括号都可以成功匹配，但是栈里面还剩个左括号没有匹配，这也是不合法的

2020年3月15日 14:54

seottle : 回复 seottle：！！！！太谢谢你了！！！！我真的没考虑到那个问题！！谢谢

2020年3月15日 15:00