文章

36

粉丝

505

获赞

55

访问

372.5k

头像
题解:括号的匹配
P1067 中山大学2019年机试题
发布于2020年3月12日 03:06
阅读数 10.0k

这道题很明显用栈来写。

遍历字符串,遇到左括号时,先和栈顶元素判断是否符合括号优先级,不符合直接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%,不知道错在哪里了,你可以看看吗crying

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 == trueprintf("YES\n");
    }
   
    return 0;
}

赞(1)

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

2020年3月15日 14:54

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

2020年3月15日 15:00