HH_Knight
HH_Knight
采纳率50%
2020-03-29 12:05

小白完全不会,求大佬指点。

已采纳

一:
如果通过插入“ +”和“ 1”可以从中得到格式正确的数学表达式,则将带括号的序列称为正确的。

例如,序列 "(())()","()"和 "(()(()))"是正确的,而")(","(()))("和"(()" 不是。

定义重新排序操作:选择括号序列的任意连续子段(子字符串),然后以任意方式对其中的所有字符进行重新排序。当重新排序的子段的长度为t时,重新排序操作需要耗时t秒。

例如,对于“))((”,他可以选择子字符串“)(”并重新排序“)()(”(此操作将花费2秒)。

不难看出,重新排序操作不会改变左括号和右括号的数量。

现在,LD想花费最少的时间,通过任意次数(可能为零)执行重新排序操作来使括号序列变成正确的。

输入格式:

1.第一行包含一个整数n(1≤n≤1e6),表示序列的长度;

2.第二行包含一个长度为n的字符串,仅由字符‘(’和‘)’组成。

输出格式:

输出一个整数,表示使括号序列正确的最小秒数;如果不可能实现,则输出-1。

输入样例:

8

))((())(

输出样例:

6

二:
给出一串包含 ( 、 ) 、[ 和 ] 的字符串,字符串在以下三种情况下为合法的:

1 字符串为空;

2 如果A和B都是合法的,那么AB也是合法的;

3 如果A是合法的,那么(A)和[A]也是合法的。

试判断输入的字符串是否合法。

输入格式:

输入包括一串由若干个 ( 、 ) 、 [ 或 ] 组成的字符串,字符串长度不超过100。

输出格式:

如果该字符串合法,输出“Yes”;否则输出“No”。

输入样例:

([])

输出样例:

Yes

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

2条回答

  • caozhy 从今以后生命中的每一秒都属于我爱的人 1年前

    第一个问题

    #include <stdio.h>
    #include <string.h>
    
    int main()
    {
        int n = 0;
        int result = 1;
        char s[100];
        scanf("%s", s);
        for (int i = 0; i < strlen(s); i++)
        {
            if (s[i] == '(') n++;
            if (s[i] == ')') n--;
            if (n < 0) { result = 0; break; }
        }
        if (n!=0) result = 0;
        if (result) printf("YES"); else printf("NO");
        return 0;
    }
    

    第二个问题

    #include <stdio.h>
    #include <string.h>
    
    char conv(char c)
    {
        if (c == ')') return '(';
        if (c == '}') return '{';
        if (c == ']') return '[';
        return 0;
    }
    
    int main()
    {
        char arr[100];
        int n = 0;
        int result = 1;
        char s[100];
        scanf("%s", s);
        for (int i = 0; i < strlen(s); i++)
        {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{')
                arr[n++] = s[i];
            else if (s[i] == ')' || s[i] == ']' || s[i] == '}')
            {
                if (arr[n - 1] != conv(s[i])) { result = 0; break; }
                n--;
            }
        }
        if (n != 0) result = 0;
        if (result) printf("YES"); else printf("NO");
        return 0;
    }
    
    
    点赞 2 评论 复制链接分享
  • ldfxxxxx ldfxxxxx 1年前

    堆栈
    1.

    #include <bits/stdc++.h>
    #define unless(a) if(!a)
    using namespace std;
    int main()
    {
        string a;
        stack <char> s;
        getline(cin, s);
        int len = a.size();
        for(int i = 0; i < len; ++i)
        {
            if(a[i] == '(') s.push(a[i]);
            else if(a[i] == ')')
            {
                unless(s.empty())
                    s.pop();
                else
                {
                    cout << "NO\n";
                    return 0;
                }
            }
    
        }
        if(s.empty()) cout << "YES";
        else cout << "NO";
        return 0;
    }
    

    2.

    #include <bits/stdc++.h>
    #define unless(a) if(!a)
    using namespace std;
    int main()
    {
        string a;
        stack <char> s;
        getline(cin, s);
        int len = a.size();
        for(int i = 0; i < len; ++i)
        {
            if(a[i] == '(') s.push(a[i]);
            else if(a[i] == ')')
            {
                unless(s.empty())
                    s.pop();
                else
                {
                    cout << "NO\n";
                    return 0;
                }
            }
        }
        unless(s.empty()) cout << "NO\n";
        for(int i = 0; i < len; ++i)
        {
            if(a[i] == '[') s.push(a[i]);
            else if(a[i] == ']')
            {
                unless(s.empty())
                    s.pop();
                else
                {
                    cout << "NO\n";
                    return 0;
                }
            }
        }
        if(s.empty()) cout << "YES\n";
        else cout << "NO\n";
        return 0;
    }
    
    点赞 1 评论 复制链接分享

相关推荐