信息奥赛题 求一个括号串有多少个有效匹配字串

billtian

信息奥赛题 求一个括号串有多少个有效匹配字串

dellric

#include "stdafx.h"

typedef struct  _SX
{
        int x;
        int y;
        char * p;
        int n;
}SX;


//char strTest[] = ")sd)xx)(as)xxff(()(sdf))(9s(s(xx)))sf(sx)(99(00";
char strTest[] = "(as)xxff(()(sdf()())))(";
int findStr(char * lp)
{
        SX sx[100];
        int i;
        int j;
        int n;
        int idxSp;
        char st[1000];
        int idxStr;
        int nStr;

        idxSp = -1;
        idxStr = 0;
        nStr = 0;
        n = strlen(lp);
        for (i = 0; i < n; i++)
        {
                if (lp[i] == '(')
                {
                        idxSp++;
                        sx[idxSp].n = 1;
                        sx[idxSp].p = &lp[i];
                        sx[idxSp].x = i;
                        sx[idxSp].y = i;
                }
                else if (lp[i] == ')')
                {
                        if (idxSp >= 0)
                        {
                                nStr++;
                                memcpy(&st[0], sx[idxSp].p, sx[idxSp].n);
                                st[sx[idxSp].n] = 0;
                                idxSp--;
                        }
                }
                else
                {
                        if (idxSp >= 0)
                        {
                                sx[idxSp].n++;
                                sx[idxSp].y++;
                        }
                }
        }
        printf("Total = %d\n", nStr);
        return nStr;
}
int main()
{
        findStr(strTest);
    return 0;
}

dellric

试试看上面的代码是不是你需要的，可以直接拷贝到VS里面运行测试。

hwarm

这题是信息学奥赛的初级还是高级的？楼主介绍一下学习经验呗。

takashiki

dellric 发表于 2020-10-19 10:59
#include "stdafx.h"

typedef struct  _SX

你这个显然不对。
比如strTest =((a)(b)(c))，按你的算法算出来是4，但实际上应该是7 ：(a)、(b)、(c)、(a)(b)、(b)(c)、(a)(b)(c)、((a)(b)(c))。如果遇到字串相同还要进一步增加复杂度。

canspider

dellric 发表于 2020-10-19 10:59
#include "stdafx.h"

typedef struct  _SX

题目理解错了，题目的意思是合法的括号串只由()这两个符号组成。可以包含，可以结合。
() 1个         S(1,2)
(()) 2个      S(2,3), S(1,4)
(()()) 4个    S(2,3) S(4,5), S(2,5), S(1,6)

如果没有学过词法分析相关内容，不要去想这道题目如何做，直接跳过就行，不寒碜

billtian

hwarm 发表于 2020-10-19 11:39
这题是信息学奥赛的初级还是高级的？楼主介绍一下学习经验呗。

没啥心得  孩子参加几年了 都是重在参与

brother_yan

还是动态规划

hwarm

billtian 发表于 2020-10-19 11:55
没啥心得  孩子参加几年了 都是重在参与

那可以啊，你家孩子多大开始学的，有没有报班，还是自己辅导的？我打算让孩子试试，准备开始学了。

billtian

hwarm 发表于 2020-10-19 16:24
那可以啊，你家孩子多大开始学的，有没有报班，还是自己辅导的？我打算让孩子试试，准备开始学了。 ...

小学五年级开始 五六年级报了两年班拿了两个小奖  初中三年学习紧竞赛帮助也不大 没有报班也没投太多精力 只参加了两次考试，现在高中了 竞赛有一定作用 打算拾起来 无奈时间比初中更少了 难啊