应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » C/C++ » 一个华为编程大赛题
172/2返回列表上一页12
查看: 1858  |  回复: 16
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

huycwork

金虫 (著名写手)
★ ★ ★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
dubo(金币+1): 谢谢交流 2011-05-29 21:43:22
微尘、梦想(金币+4): 谢谢参与！ 2011-05-30 17:55:00
俺来个递归各种复杂版，不确定的状态机真是麻烦透了。免分析，直接上代码，C++版本：
CODE:
#include
#include
using namespace std;
/*
* 参数说明
* str为待匹配字符串
* reg为通配符表达式
* is为str的当前索引，即从第is个字符开始匹配
* ir为reg的当前索引，即从第ir个字符开始匹配
*/
bool reg_match(const string &str, const string ®, size_t is = 0, size_t ir = 0){
        if(ir == reg.size() - 1){
                //*是贪婪的，以*结尾的任何表达式都表示匹配
                if(reg.back() == '*')
                        return true;
                //以?结尾的reg遇到字符串结尾也表示匹配
                if((reg.back() == '?')&&(is == str.size()-1))
                        return true;
                //reg和str的尾字符匹配
                if(is == str.size() - 1)
                        return str.back() == reg.back();
        }
        bool res = false;
        char flagc;
        for(size_t i = is; i < str.size(); ++i){
                switch(reg.at(ir)){
                case '*':
                        //设置标志，*后面的第一个标志定位什么时候开始下一层匹配
                        if(reg.at(ir+1) == '?'){
                                if(reg.size() == ir+2)
                                        return true;
                                flagc = reg.at(ir+2);
                        }else{
                                flagc = reg.at(ir+1);
                        }
                        //贪婪匹配，吃掉遇到flag之前的任何操作符之后匹配下一层
                        for(size_t rsi = str.size() - 1; rsi >= is; --rsi){
                                if(str.at(rsi) == flagc){
                                        if(reg_match(str, reg, rsi, ir+1))
                                                return true;
                                }
                        }
                        return false;
                case '?':
                        //0匹配和1匹配，优先1匹配
                        if(reg_match(str, reg, is+1, ir+1))
                                return true;
                        return reg_match(str, reg, is, ir+1);
                default:
                        //其余字符取相等匹配
                        if(str.at(is) == reg.at(ir))
                                return reg_match(str, reg, is+1, ir+1);
                        return false;
                }
        }
        return false;     //免编译错误，应排版需要的尾巴
}

int main(){
        using namespace std;
        string str("ababacdbadcbaecdef");
        string reg("ab*c*a?e*f");
        cout<         return 0;
}

说明：
*为贪婪符号，?也是贪婪的，这就是说，*.txt会完整匹配abc.txt.txt，?c会优先匹配ac而不是c。
意思就大概是这个意思了，根据给出的通配表达式，对应到正则表达式，如：
ab*c*a?e*f => ab.*c.*a.?e.*f

欢迎指点讨论。

[ Last edited by huycwork on 2011-5-29 at 21:57 ]
赞一下(3人) 回复此楼
漩涡的中心有一块空地，空空的。
11楼2011-05-29 21:35:14
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

460104898

铜虫 (正式写手)
有谁可以用C写一个啊？
大家一起交流下。
赞一下 回复此楼
囚
12楼2011-05-30 11:57:11
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★ ★ ★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想(金币+5): 谢谢参与！ 2011-05-30 17:55:24
写了一个C的，不过，没有严格测试。而且我改了通配的意思，也就是?代表一个字符，*代表至少一个字符。另外有一个假设，那就是*后面不是通配符。
CODE:
#include
#include

#define BUFSZ 1000

int main(int argc, char** argv) {
    char str[BUFSZ], re[BUFSZ];
    char *pStr, *pRe;
    int lenStr, lenRe;
    int stat = 0;

    memset(str, BUFSZ, 0);
    memset(re , BUFSZ, 0);

    pStr = str;
    pRe  = re;

    printf("Input match string:");
    scanf("%s", re);
    lenRe = strlen(re);

    printf("Input string to match:");
    scanf("%s", str);
    lenStr = strlen(str);

    while ((pRe - re) < lenRe && (pStr - str) < lenStr && stat == 0) {
        printf("%c, %c\n", *pRe, *pStr);
        switch(*pRe) {
            case '*':
                pRe++;
                while(*pStr != *pRe && (pStr - str) < lenStr) pStr++;
                break;
            case '?':
                pRe++;
                pStr++;
                break;
            default:
                if(*pRe++ != *pStr++) {
                    puts("Not Match");
                    stat = 1;
                }
                break;
        }
    }
    if(stat == 0) puts("Match");
    return 0;
}

[ Last edited by holmescn on 2011-5-30 at 13:47 ]
赞一下(2人) 回复此楼
13楼2011-05-30 13:37:46
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

460104898

铜虫 (正式写手)
★ ★ ★ ★ ★
微尘、梦想(金币+5): 谢谢参与！ 2011-05-30 17:55:48
int GetMatchStr(const char* ArrStr,const char* KeyStr)
{
    switch (*KeyStr)
    {
    case '\0':
        return (*ArrStr=='\0')? 1:0;
    case '?':
        return (*ArrStr=='\0')? 0:GetMatchStr(ArrStr+1,KeyStr+1);
    case '*':
        return (*ArrStr=='\0')? GetMatchStr(ArrStr,KeyStr+1):
            GetMatchStr(ArrStr+1,KeyStr)|GetMatchStr(ArrStr,KeyStr+1);
    default:
        return (*ArrStr!=*KeyStr)? 0:GetMatchStr(ArrStr+1,KeyStr+1);
    }
}
赞一下(1人) 回复此楼
囚
14楼2011-05-30 17:11:15
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

460104898

铜虫 (正式写手)
上面一个是我同学用递归写的。。
想当犀利啊。
赞一下 回复此楼
囚
15楼2011-05-30 17:12:04
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
jjdg(金币+1): 感谢参与 2011-05-31 00:27:54
引用回帖:
Originally posted by 460104898 at 2011-05-30 17:11:15:
int GetMatchStr(const char* ArrStr,const char* KeyStr)
{
    switch (*KeyStr)
    {
    case '\0':
        return (*ArrStr=='\0')? 1:0;
    case '?':
        return (*ArrStr=='\0')? 0:GetMat ...

你说的C代码就是这个意思啊？
这种代码就是那种省硬盘并且没有办法优化也不打算让别人优化的代码，再带上安全性稍微差一些。早知道就该给你这种代码，不管怎么说，少了几行：
CODE:
int matchStr(const char *str, const char *reg){
  if(*reg == '?'){
    return *str && matchStr(str+1, reg+1) || matchStr(str, reg+1);
  }else if(*reg == '*'){
    return *str ? matchStr(str+1, reg) || matchStr(str, reg+1) : 1;
  }
  return (*str == *reg) && (*str == 0) ? matchStr(str+1, reg+1) : 0;
}

[ Last edited by huycwork on 2011-5-31 at 10:12 ]
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
16楼2011-05-30 18:09:24
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
jjdg(金币+1): 感谢参与 2011-05-31 00:28:02
修改了一下，现在只是一个Just Run的版本。可能会有Bug
CODE:
#include

#define BUFSZ 1000

int main(int argc, char** argv) {
    char str[BUFSZ], re[BUFSZ];
    char *pStr, *pRe;
    char *pStr0;
    int stat = 0;

    memset(str, BUFSZ, 0);
    memset(re , BUFSZ, 0);

    pStr = str;
    pStr0= str;
    pRe  = re;

    printf("Input match string:");
    scanf("%s", re);

    printf("Input string to match:");
    scanf("%s", str);

    while (*pRe != '\0' && *pStr != '\0' && pStr0 != '\0' && stat == 0) {
        printf("%c, %c, %c\n", *pRe, *pStr, *pStr0);
        switch(*pRe) {
            case '*':
                pRe++;
                if (*pRe == '*' || *pRe == '?') break;
                while(*pStr != *pRe && *pStr != '\0') pStr++;
                break;
            case '?':
                pRe++;
                pStr++;
                break;
            default:
                if(*pRe != *pStr++ && *pRe != *pStr0++) {
                    stat = 1;
                }
                pRe++;
                break;
        }
    }
    if(stat == 0)
        puts("Match");
    else
        puts("Not Match");
    return 0;
}

我觉得应该给一组testcase，这样有个标准测试。

[ Last edited by holmescn on 2011-5-30 at 23:29 ]
赞一下(2人) 回复此楼
17楼2011-05-30 23:27:31
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 460104898 的主题更新
172/2返回列表上一页12
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
信息提示
关闭
请填处理意见
关闭