📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 1668| 回复: 10
跳转到指定楼层
上一主题 下一主题
收起左侧

求解:字符串解析

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
有字符串:         A={B=12;S=23;H=13;E={A=100;F={G=1;}};D=50;};
可以求得:
         A.B=12
         A.S=23
         A.E.A=100
         A.E.F.G=1


求如何构造这个算法?
求解~

上一篇:Run Time Error in Add Two Numbers(Only in new oj)?
下一篇:求解:出牌算法
🔗
北美农民 2013-9-24 10:25:02 | 只看该作者
全局:
没看懂题。。。。。
回复

使用道具 举报

🔗
 楼主| zyp911 2013-9-24 10:42:15 | 只看该作者
全局:
北美农民 发表于 2013-9-24 10:25
没看懂题。。。。。

哪里没看懂呢?

回复

使用道具 举报

🔗
 楼主| zyp911 2013-9-24 10:45:44 | 只看该作者
全局:
北美农民 发表于 2013-9-24 10:25
没看懂题。。。。。

有一个结构化的字符串,例如: A={B=12;S=23;H=13;E={A=100;F={G=1;}};D=50;};
表达式:
A.B = 12
A.S = 23
A.H = 23
A.E.A=100
A.E.F.G=1
A.D=50

问题是:当输入类似一个字符串后,求出类似表达式的值?
回复

使用道具 举报

🔗
北美农民 2013-9-24 11:16:31 | 只看该作者
全局:
zyp911 发表于 2013-9-23 21:45
有一个结构化的字符串,例如: A={B=12;S=23;H=13;E={A=100;F={G=1;}};D=50;};
表达式:
A.B = 12

DFS吧,拿到第一个字母, 因为是固定得。。  以分号为界拆开, 如果遇到{}就递归到下一层, 继续拆开, 没有遇到就生成答案。
回复

使用道具 举报

🔗
 楼主| zyp911 2013-9-24 14:09:39 | 只看该作者
全局:
北美农民 发表于 2013-9-24 11:16
DFS吧,拿到第一个字母, 因为是固定得。。  以分号为界拆开, 如果遇到{}就递归到下一层, 继续拆开, 没 ...

写来看看?
考虑复杂性
这样是否最优?
回复

使用道具 举报

🔗
vng 2013-9-24 17:41:12 | 只看该作者
全局:
void parse_str(const char * str)
{
        char letter[26] ;
        char output[128]; //make sure the length is adequate.
        int  n = 0;

        int i, j , k;
        while(str[i++])
        {
                switch (str[i])
                {
                case '=' :
                        i ++;
                        if(isdigit(str[i])
                        {
                                k = 0;
                                for(int j = 0; i < n ; j ++)
                                {
                                        output[k++] = letter[j];
                                        output[k++] = '.';
                                }
                                output[k++] = str[i-2];
                                output[k++] = '.';

                                while(str[i] != ';')
                                {
                                        output[k++] = str[i++];
                                }
                                printf("%s\n",output);
                                continue;
                        }
                        else
                        {
                                letter[n] = str[i-2];
                                n ++;
                        }
                case ';':
                        break;
                case '}':
                        n --;
                        break;
                default:
                        ;
                }
        }
}
回复

使用道具 举报

🔗
 楼主| zyp911 2013-9-24 20:34:20 | 只看该作者
全局:
vng 发表于 2013-9-24 17:41
void parse_str(const char * str)
{
        char letter[26] ;

for(int j = 0; i < n ; j ++)

这个循环什么意思?

似乎没有解决嵌套“{}”的问题啊?

能否再详细些?
回复

使用道具 举报

🔗
mymiracle 2013-9-24 22:09:14 | 只看该作者
全局:
/********************************************************************
* function: ParseString
* purpose:  Get the value of an expression according to a structured string
* retval:   char* : A string of numbers, return NULL if no result
* params:
*           const char* strStructuredString : "A={B=12;S=23;H=13;E={A=100;F={G=1;}};D=50;};"
*                         const char* strExpression : "A.E.F.G=1"
********************************************************************/
char* ParseString(const char* strStructuredString, const char* strExpression)
{
        int iDepth = 0;
        int i = 0;
        while (strExpression[i] != '\0')
        {
                if (strExpression[i] == '.')
                {
                        iDepth ++;
                }
                i ++;
        }
        iDepth ++;
        char* arrExpression = new char[iDepth];
        for (i = 0; i < iDepth; i ++)
        {
                arrExpression[i] = strExpression[i * 2];
        }
       
        i = 0;
        int iCountOfBrace = 0;
        bool* arrMatch = new bool[iDepth];
        for (int i = 0; i < iDepth; i ++)
        {
                arrMatch[i] = false;
        }
        while (strStructuredString[i] != '\0')
        {
                if (strStructuredString[i] == '{')
                {
                        arrMatch[iCountOfBrace] = strStructuredString[i - 2] == arrExpression[iCountOfBrace];
                        iCountOfBrace ++;
                }
                else if (strStructuredString[i] == '}')
                {
                        iCountOfBrace --;
                }
                else
                {
                        if (iCountOfBrace == iDepth - 1)
                        {
                                if (strStructuredString[i] == '=')
                                {
                                        if (strStructuredString[i - 1] == arrExpression[iDepth - 1])
                                        {
                                                bool bFound = true;
                                                for (int j = 0; j < iDepth - 1; j ++)
                                                {
                                                        if (!arrMatch[j])
                                                        {
                                                                bFound = false;
                                                                break;
                                                        }
                                                }
                                                if (bFound)
                                                {
                                                        int j = i + 1;
                                                        char* strReVal = new char[64];
                                                        while (strStructuredString[j] != ';')
                                                        {
                                                                strReVal[j - i - 1] = strStructuredString[j];
                                                                j ++;
                                                        }
                                                        strReVal[j - i - 1] = '\0';
                                                       
                                                        delete [] arrExpression;
                                                        delete [] arrMatch;
                                                        return strReVal;
                                                }
                                        }
                                }
                        }
                }
                i ++;
        }
       
        delete [] arrExpression;
        delete [] arrMatch;
        return NULL;
}

好久不写这种像编译原理的算法了,工作中很少用到。
复杂度应该是O(n^2)?忘了复杂度怎么算的,反正嵌套了一个循环。

评分

参与人数 1大米 +3 收起 理由
smallheart00 + 3 回答的很好!

查看全部评分

回复

使用道具 举报

🔗
 楼主| zyp911 2013-9-25 07:40:43 | 只看该作者
全局:
mymiracle 发表于 2013-9-24 22:09
/********************************************************************
* function: ParseString
*  ...

非常感谢
仔细研究中
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表