Hello World
Spiga

趣味编程:从字符串中提取信息(参考答案 - 上)

2009-10-21 01:13 by 老赵, 20337 visits

这次“趣味编程”的目的是解析字符串,从一个指定模式的字符串中提取信息。对于目前这个问题,解决方案有很多种,例如直接拆分,使用正则表达式,或是如现在本文这般按照顺序解析。总结果上来说,这些做法都是可取的,不过现在我打算举出的做法是我认为最为“典型”也最有“学习”和“展现”价值的解决方案:基于状态机的顺序字符解析。也欢迎您对此其他的做法进行深入分析。

您可能需要重新阅读上一篇文章来回忆字符串解析的具体规则,起始归纳起来,它只有以下三点:

  1. 一个text由一至多个token group组成;一个token group由一至多个token组成。
  2. token group的token之间使用单条横线“-”进行分割;text的token group之间使用两条横线“--”进行分割。
  3. token可以使用单引号包裹,单引号包裹内的横线作为普通字符处理,单引号包裹内使用两个单引号表示单个单引号。

至于最终结果,便是将一个text字符串,拆分成一个token group列表:

static List<List<string>> Parse(string text) { ... }

在这里,我们使用List<string>来表示一个token group(即token列表)。自然,表现方式可以有所不同。例如您的Parse方法如果返回“列表的数组”、“数组的列表”或是“数组的数组”都是没有任何问题的。

下面的做法基于winter-cn在上一篇文章后面的回复,再加以简单的修改和注释后得到的结果。这个做法的思路和我在“出题”时已经准备的“参考答案”不谋而合,但是winter-cn的实现要比我的更为简单、因此我的代码就不拿出来献丑了,我们现在一起来欣赏高手的劳动成果。

winter-cn的做法,是将“解析”工作拆分为5种状态,每种状态对应一种解析逻辑,而每种解析逻辑除了处理当前字符(改变一些公共状态)以外,还会返回处理下一个字符所使用的“解析逻辑”——这就是状态的迁移。winter-cn原有的做法是使用Func<char, object>来表示解析逻辑的类型,这样在每次得到新状态之后,还需要将其转化为Func<char, object>。不过为了更清晰地表达这样一种逻辑,我们也可以定义一个返回自身类型的“递归”的委托类型:

delegate StateParser StateParser(char ch);

在现在的实现中,我们把它解析过程分解为5个状态,分别对应不同“时刻”下的解析逻辑:

static List<List<string>> Parse(string text)
{
    StateParser p1 = null; // 用于解析token的起始字符
    StateParser p2 = null; // 用于解析作为分隔符的“-”的下一个字符
    StateParser p3 = null; // 用于解析token中或结尾的单引号的下一个字符
    StateParser p4 = null; // 用于解析单引号外的token字符
    StateParser p5 = null; // 用于解析单引号内的token字符

    var currentToken = new StringBuilder(); // 用于构建当前的token(即收集字符)
    var currentTokenGroup = new List<string>(); // 用于构建当前的token group(即收集token)
    var result = new List<List<string>>(); // 用于保存结果(即收集token group)
    ...

    return result;
}

p1至p5便是所谓的“状态”,也就是“解析逻辑”,它们都会操作currentToken,currentTokenGroup和result三个数据,并返回下一个状态。状态的划分并非只有一种,不同的状态划分方式会形成不同的逻辑。我们接下来便要根据这样的划分方式,为每个状态指定实现了。在实现的过程中,我们需要时刻遵守“当前”状态的逻辑细节,以及其他状态的职责,这样实现状态的迁移似乎也并不是一件困难的事情。

首先是p1,它的作用是解析token的第一个字符:

// 解析token的起始字符
p1 = ch =>
{
    if (ch == '-')
    {
        // 如果token中需要包含单引号或“-”,
        // 那么这个token在表示的时候一定需要用一对单引号包裹起来
        throw new ArgumentException();
    }

    if (ch == '\'')
    {
        // 如果起始字符是单引号,
        // 则开始解析单引号内的token字符
        return p5;
    }
    else
    {
        // 如果是普通字符,则作为当前token的字符,
        // 并开始解析单引号外的token字符
        currentToken.Append(ch);
        return p4;
    }

};

接着是p2:它的作用是解析分隔符“-”(不包括单引号包裹内的“-”)后的下一个字符:

// 解析作为分隔符的“-”的下一个字符
p2 = ch =>
{
    if (ch == '-')
    {
        // 如果当前字符为“-”,说明一个token group结束了(因为前一个字符也是“-”),
        // 则将当前的token group加入结果集,并且准备新的token group
        result.Add(currentTokenGroup);
        currentTokenGroup = new List<string>();
        return p1;
    }
    else if (ch == '\'')
    {
        // 如果当前字符为单引号,则说明新的token以单引号包裹
        // 则开始解析单引号内的token字符
        return p5;
    }
    else
    {
        // 如果是普通字符,则算作当前token的字符,
        // 并继续解析单引号外的token字符
        currentToken.Append(ch);
        return p4;
    }
};

接着是p3:解析token内部或结尾的单引号的下一个字符:

// 解析token内部或结尾的单引号的下一个字符
p3 = ch =>
{
    if (ch == '\'')
    {
        // 如果当前字符为单引号,则说明连续两个单引号,
        // 所以表明token中出现了“单个”单引号,并且当前token一定包裹在单引号内,
        // 因此继续解析单引号内的token字符
        currentToken.Append('\'');
        return p5;
    }
    else if (ch == '-')
    {
        // 如果当前字符为一个分隔符,则说明上一个token已经结束了
        // 于是将当前token加入当前token group,准备新的token,
        // 并解析分隔符后的下一个字符
        currentTokenGroup.Add(currentToken.ToString());
        currentToken = new StringBuilder();
        return p2;
    }
    else
    {
        // 单引号后面只可能是另一个单引号或者一个分隔符,
        // 否则说明输入错误,则抛出异常
        throw new ArgumentException();
    }
};

最后则是p4和p5,分别用于处理普通的token以及被单引号包裹的token字符:

// 用于解析单引号外的token字符,
// 即一个没有特殊字符(分隔符或单引号)的token
p4 = ch => 
{
    if (ch == '\'')
    {
        // 如果token中出现了单引号,则抛出异常
        throw new ArgumentException();
    }

    if (ch == '-')
    {
        // 如果出现了分隔符,则表明当前token结束了,
        // 于是将当前token加入当前token group,准备新的token,
        // 并解析分隔符的下一个字符
        currentTokenGroup.Add(currentToken.ToString());
        currentToken = new StringBuilder();
        return p2;
    }
    else
    {
        // 对于其他字符,则当作token中的普通字符处理
        // 继续解析单引号外的token字符
        currentToken.Append(ch);
        return p4;
    }
};

// 用于解析单引号内的token字符
p5 = ch =>
{
    if (ch == '\'')
    {
        // 对于被单引号包裹的token内的第一个单引号,
        // 需要解析其下一个字符,才能得到其真实含义
        return p3;
    }
    else
    {
        // 对于普通字符,则添加到当前token内
        currentToken.Append(ch);
        return p5;
    }
};

这些状态中的逻辑都有一个特点,它们都会通过C#编译器形成的闭包来操作“外部”状态——不过这个“外部”是指这些匿名函数的外部,但是它们统统属于Parse方法本身!这意味着,虽然我们的状态并非“纯函数”,但是Parse方法是没有任何副作用(Side Effect,即除了返回值外不会影响其他外部状态,以及相同的返回值永远相同的结果)。这个特点确保了Parse方法可以被任意多个线程同时调用。winter-cn的做法巧妙地使用了C#编译器的特性,简化了Parse方法的实现。

在定义完5种状态之后,我们便要从p1开始依次处理字符串中的每个字符,并且随着状态的迁移改变处理每个字符的逻辑。当然,最后的“收尾”工作也是必不可少的:

static List<List<string>> Parse(string text)
{
    ...

    text.Aggregate(p1, (sp, ch) => sp(ch));

    currentTokenGroup.Add(currentToken.ToString());
    result.Add(currentTokenGroup);

    return result;
}

可以看出,这种做法的优势之一是完全的“顺序处理”,只遍历一次。如果您使用字符串的分割或者正则表达式进行解析的话,一般总是会有“回溯”,以及拆分出更多的字符串。因此,根据推测,这个做法从性能上来讲应该也有一定优势,不过还是需要真实的性能比较才能得出确切的结果。本文全部代码已经存放在http://gist.github.com/214427中,您可以复制、执行,调试等等。

这次的“趣味编程”是到目前为止最为热闹的一次,在上一篇文章的回复里您还可以发现许多朋友给出的大量解决方案,不过由于时间精力有限,我无法一一浏览了。此外,由于winter-cn已经给出了与我思路接近但实现更好的做法,后来我又用F#实现了另外一个思路不同的版本,您会发现F#有一些语言特性似乎非常适合进行字符串解析工作,它对于我们编写C#代码也有一定的借鉴意义。

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

62 条回复

  1. 卡索
    *.*.*.*
    链接

    卡索 2009-10-21 01:21:00

    终于赶上一次老赵的沙发啦!再先占位慢慢品...

  2. winter-cn
    *.*.*.*
    链接

    winter-cn 2009-10-21 01:43:00

    坐了次板凳 对楼上无限怨念中

    非常荣幸咱的解决方案跟老赵一致了

    既然是状态机 我觉得有个状态迁移图比较好 我自己写程序的时候是在纸上画了艹图的

    建议老赵下把搞一个四则运算加括号的词法分析 这样更有意思

  3. 我是一只小老虎 喵!
    *.*.*.*
    链接

    我是一只小老虎 喵! 2009-10-21 03:20:00

    劫匪哥仍旧在走高端路线.两年了
    这些日子写了Nhibernate,小老虎一阵精喜,难道劫匪哥开始平民化了?
    这不,又来啦.
    看不懂呀,这可怎么办撒 .-_-.

  4. 初始小花
    *.*.*.*
    链接

    初始小花 2009-10-21 08:25:00

    字符串是我最感兴趣的东西,前排占个座慢慢看。

  5. Jimixu
    *.*.*.*
    链接

    Jimixu 2009-10-21 08:27:00

    同意2L的说法,状态机必须先画好状态图,理清逻辑,就清晰多了

  6. killkill
    *.*.*.*
    链接

    killkill 2009-10-21 08:31:00

    --------------------------------------------------
    这种做法的优势之一是完全的“顺序处理”,只遍历一次。
    --------------------------------------------------

    不过太难维护了。 没有Winter-Cn 和 您这种优美
    :<

  7. 侯垒
    *.*.*.*
    链接

    侯垒 2009-10-21 08:38:00

    也来顶一把。

  8. Hawkon
    *.*.*.*
    链接

    Hawkon 2009-10-21 08:45:00

    老赵你真是个高产博主,怎么会有这么多的时间写文章。

  9. 老赵
    admin
    链接

    老赵 2009-10-21 09:05:00

    @winter-cn
    是啊是啊,昨天晚上太晚了,一会儿补一个。

  10. 老赵
    admin
    链接

    老赵 2009-10-21 09:07:00

    @killkill
    嗯?我就是在说winter-cn的做法啊。

  11. 小瘦[未注册用户]
    *.*.*.*
    链接

    小瘦[未注册用户] 2009-10-21 09:11:00

    哈哈哈,就是喜欢看这些文章,支持老赵了

  12. _龙猫
    *.*.*.*
    链接

    _龙猫 2009-10-21 09:13:00

    不是假设输入都是正确的么,为什么还有抛出异常?
    这种解法真是让人看得崩溃

  13. Galactica
    *.*.*.*
    链接

    Galactica 2009-10-21 09:14:00

    我觉得写写框架相关,产品相关的技术文章就差不多了.

    像这种课本知识类的文章,没必要铺开来写,毕竟修过《编译原理》
    的人都知道怎么做。

  14. 老赵
    admin
    链接

    老赵 2009-10-21 09:18:00

    @_龙猫
    更完整自然更好了。
    这可不能崩溃啊,这个是再普通不过的东西了。
    程序员必知必会。

  15. 老赵
    admin
    链接

    老赵 2009-10-21 09:19:00

    @Galactica
    框架相关,产品相关的东西,看文档就差不多了。
    在我看来吧,什么知识不是课本知识?只要是实际会用到的就该拿出来玩玩。
    修过《编译原理》的人都知道怎么做,可能没错,但是……
    我估计普通程序员中10个有8个是不知道或写不出的吧,呵呵。

  16. 老赵
    admin
    链接

    老赵 2009-10-21 09:23:00

    @我是一只小老虎 喵!
    NHibernate就平民化了吗?
    看不懂就说明有东西可学了啊,有前进目标了,多好。

  17. 老赵
    admin
    链接

    老赵 2009-10-21 09:31:00

    Hawkon:老赵你真是个高产博主,怎么会有这么多的时间写文章。


    http://www.cnblogs.com/JeffreyZhao/archive/2009/10/16/talk-about-blogging.html

  18. 初手[未注册用户]
    *.*.*.*
    链接

    初手[未注册用户] 2009-10-21 09:33:00

    没看到这个扩展
    text.Aggregate

  19. Cat Chen
    *.*.*.*
    链接

    Cat Chen 2009-10-21 09:37:00

    @Jeffrey Zhao
    普通程序员里10里面有多少个是认真上过编译原理的呢……

  20. 老赵
    admin
    链接

    老赵 2009-10-21 09:50:00

    @初手
    看一下System.Linq命名空间。

  21. winter-cn
    *.*.*.*
    链接

    winter-cn 2009-10-21 10:02:00

    Cat Chen:
    @Jeffrey Zhao
    普通程序员里10里面有多少个是认真上过编译原理的呢……


    就是呢 上学的时候都没好好听
    不过大多数老师也是照本宣科

  22. 麒麟.NET
    *.*.*.*
    链接

    麒麟.NET 2009-10-21 10:15:00

    那天看到题目时,觉得也应该用状态机实现,于是整了一堆状态类……怎么就想不到用这种轻量级的实现方式呢?

  23. 老赵
    admin
    链接

    老赵 2009-10-21 10:16:00

    @winter-cn
    不过我有时候反而觉得,不是许多人一直抱怨老师没水平吗?
    但是课本都是非常好的啊,甚至和顶级大学是一样的,那么……就老老实实把课本看好就够了啊,呵呵。

  24. 老赵
    admin
    链接

    老赵 2009-10-21 10:17:00

    @麒麟.NET
    或者状态“方法”也是可以的,比如就一个类。
    这里更轻,用了状态“委托”。

  25. winter-cn
    *.*.*.*
    链接

    winter-cn 2009-10-21 10:19:00

    Galactica:
    我觉得写写框架相关,产品相关的技术文章就差不多了.

    像这种课本知识类的文章,没必要铺开来写,毕竟修过《编译原理》
    的人都知道怎么做。


    大学学的多了

    密码学——能写出DES的举手
    数据结构——能写出B+树的举手
    算法——能写出网络流的举手
    编译原理——能写出LLR的举手
    操作系统——能写出LRU以及银行家算法的举手
    人工智能——能写出A*的举手

  26. winter-cn
    *.*.*.*
    链接

    winter-cn 2009-10-21 10:27:00

    Jeffrey Zhao:
    @winter-cn
    不过我有时候反而觉得,不是许多人一直抱怨老师没水平吗?
    但是课本都是非常好的啊,甚至和顶级大学是一样的,那么……就老老实实把课本看好就够了啊,呵呵。



    即使东抄西抄的那种课本 其实不少也是值得一读的
    至少它的源头是好东西

  27. 老赵
    admin
    链接

    老赵 2009-10-21 10:27:00

    @winter-cn
    太恶毒了啊,这不是逼别人说自己“不举”么……

  28. winter-cn
    *.*.*.*
    链接

    winter-cn 2009-10-21 10:47:00

    Jeffrey Zhao:
    @winter-cn
    太恶毒了啊,这不是逼别人说自己“不举”么……


    其实我自己也......

  29. Gnie
    *.*.*.*
    链接

    Gnie 2009-10-21 11:39:00

    对中文解析如何?

  30. JimLiu
    *.*.*.*
    链接

    JimLiu 2009-10-21 11:41:00

    这不是有穷自动机吗?哈哈!编译原理来了!我很喜欢的课程。

  31. vczh[未注册用户]
    *.*.*.*
    链接

    vczh[未注册用户] 2009-10-21 11:45:00

    上个月曾经在公司写unittest的时候,给C#来了一个简单的库,在程序里面写语法,然后parser就构造出来了……

    老赵的解决方案可以通过写出正则表达式之后,人肉编译成DFA搞定

  32. JimLiu
    *.*.*.*
    链接

    JimLiu 2009-10-21 11:46:00

    顺便凑个热闹

    密码学——能写出DES的举手——举手不能,没学过
    数据结构——能写出B+树的举手——只会B-树,啧啧
    算法——能写出网络流的举手——最简单的可以,不过算法博大精深,光一个网络流不足为奇,啧啧
    编译原理——能写出LLR的举手——LL,LR0,LR1,LALR,SLR全写过……噢不对,LL那个消除递归和公公因子的太麻烦了,所以LL没写。SLR也没写,因为最后的编译器用LALR了。
    操作系统——能写出LRU以及银行家算法的举手——银行家简单,LRU没写过,但是这个也不难
    人工智能——能写出A*的举手——这个比较简单了

  33. 老赵
    admin
    链接

    老赵 2009-10-21 11:52:00

    @vczh
    话说,这东西正则咋写?

  34. JimLiu
    *.*.*.*
    链接

    JimLiu 2009-10-21 11:55:00

    @Jeffrey Zhao
    我感觉用两个或两个以上符号表示Separator的正则是非常难的。
    当初和我同学一起研究如何写一个表示C++块注释/* .. */的正则表达式,想了很久很久,才弄出个很蹩脚的来。

  35. winter-cn
    *.*.*.*
    链接

    winter-cn 2009-10-21 12:24:00

    JimLiu:
    顺便凑个热闹

    密码学——能写出DES的举手——举手不能,没学过
    数据结构——能写出B+树的举手——只会B-树,啧啧
    算法——能写出网络流的举手——最简单的可以,不过算法博大精深,光一个网络流不足为奇,啧啧
    编译原理——能写出LLR的举手——LL,LR0,LR1,LALR,SLR全写过……噢不对,LL那个消除递归和公公因子的太麻烦了,所以LL没写。SLR也没写,因为最后的编译器用LALR了。
    操作系统——能写出LRU以及银行家算法的举手——银行家简单,LRU没写过,但是这个也不难
    人工智能——能写出A*的举手——这个比较简单了


    哈哈 高手 好学生

  36. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-10-21 12:55:00

    状态机谁都会,用函数(委托)来表示状态就不是谁都会了。

  37. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-10-21 17:34:00

    今天用winform写了一个tooltip
    悬浮半秒显示 离开半秒隐藏

    用了四个状态

    Hidden
    ShowWaiting
    Showing
    HideWaiting


    using System;
    using System.Collections.Generic;
    using System.ComponentModel;
    using System.Data;
    using System.Drawing;
    using System.Text;
    using System.Windows.Forms;
    
    namespace CFETS.NGCNYTS.SelfHealthing
    
    {
    
    
    
    
        public partial class TipForm : Form
        {
    
    
    
            public enum UserAction
            {
                Enter,
                Leave,
            }
    
            public enum ShowStatus
            {
                Hidden,
                ShowWaiting,
                Showing,
                HideWaiting
            }
    
            delegate void StatusDelegate(TipForm thisForm, Control targetControl);
    
            System.Threading.Timer StatusChangeTimer;
    
    
            public ShowStatus CurrentStatus { get; set; }
            public Control CurrentControl { get; set; }
    
            public int ShowDelay { get; set; }
            public int HideDelay { get; set; }
    
            delegate void CallBack(object theDelegate);
    
    
            Dictionary<ShowStatus, StatusDelegate> EnterActions = new Dictionary<ShowStatus, StatusDelegate>();
            Dictionary<ShowStatus, StatusDelegate> LeaveActions = new Dictionary<ShowStatus, StatusDelegate>();
    
    
            public void BeginDoAction(UserAction action, Control control)
            {
                if (!(object.ReferenceEquals(CurrentControl, control)))
                {
                    this.CurrentStatus = ShowStatus.Hidden;
                }
    
                StatusDelegate innersl = ((action == UserAction.Enter) ? EnterActions : LeaveActions)[CurrentStatus];
                innersl(this, control);
    
    
    
    
    
            }
    
    
    
    
            static TipForm()
            {
                Control.CheckForIllegalCrossThreadCalls = false;
            }
    
            public void Show(TipForm thisForm, Control targetControl)
            {
                base.Hide();
                CurrentControl = targetControl;
                Point loc = MousePosition;
                
    
                this.Location = loc;
                this.Show(targetControl.FindForm());
                CurrentStatus = ShowStatus.Showing;
    
            }
            public new  void Hide()
            {
                base.Hide();
                this.CurrentStatus = ShowStatus.Hidden;
            }
    
    
    
            public TipForm(int showDelay, int hideDelay)
            {
                Size s = this.Size;
                this.Size = new Size(0, 0);
                this.Show();
                this.Hide();
                this.Size = s;
                this.CurrentStatus = ShowStatus.Hidden;
                this.ShowDelay = showDelay;
                this.HideDelay = hideDelay;
                EnterActions.Add
                    (
                        ShowStatus.Hidden,
                        delegate(TipForm thisForm, Control targetControl)
                        {
                            CurrentStatus = ShowStatus.ShowWaiting;
                            int delay = ShowDelay;
                            if (StatusChangeTimer != null)
                            {
                                StatusChangeTimer.Change(-1, -1);
                                StatusChangeTimer.Dispose();
                                StatusChangeTimer = null;
                            }
                            CallBack cb = delegate(object o)
                            {
                                Show(this, targetControl);
    
                            };
                            StatusChangeTimer = new System.Threading.Timer(new System.Threading.TimerCallback(cb), null, delay, -1);
    
                        }
                    );
    
                EnterActions.Add
                    (
                        ShowStatus.ShowWaiting,
                        delegate(TipForm thisForm, Control targetControl)
                        { }
                    );
                EnterActions.Add
                   (
                       ShowStatus.Showing,
                       delegate(TipForm thisForm, Control targetControl)
                       { }
                   );
    
                EnterActions.Add
               (
                   ShowStatus.HideWaiting,
                   delegate(TipForm thisForm, Control targetControl)
                   {
                       if (StatusChangeTimer != null)
                       {
                           StatusChangeTimer.Change(-1, -1);
                           StatusChangeTimer.Dispose();
                           StatusChangeTimer = null;
                       }
                       CurrentStatus = ShowStatus.Showing;
                   }
               );
    
                LeaveActions.Add
                        (
                            ShowStatus.Hidden,
                            delegate(TipForm thisForm, Control targetControl)
                            {
                               
                            }
                        );
    
                LeaveActions.Add
                    (
                        ShowStatus.ShowWaiting,
                        delegate(TipForm thisForm, Control targetControl)
                        {
                            if (StatusChangeTimer != null)
                            {
                                StatusChangeTimer.Change(-1, -1);
                                StatusChangeTimer.Dispose();
                                StatusChangeTimer = null;
                            }
                            CurrentStatus = ShowStatus.Hidden ;
                        }
                    );
                LeaveActions.Add
                   (
                       ShowStatus.Showing,
                       delegate(TipForm thisForm, Control targetControl)
                       {
                           CurrentStatus = ShowStatus.HideWaiting ;
                           int delay = HideDelay ;
                           if (StatusChangeTimer != null)
                           {
                               StatusChangeTimer.Change(-1, -1);
                               StatusChangeTimer.Dispose();
                               StatusChangeTimer = null;
                           }
                           CallBack cb = delegate(object o)
                           {
                               Hide();
    
                           };
                           StatusChangeTimer = new System.Threading.Timer(new System.Threading.TimerCallback(cb), null, delay, -1);
    
                       
                       }
                   );
    
                LeaveActions.Add
               (
                   ShowStatus.HideWaiting,
                   delegate(TipForm thisForm, Control targetControl)
                   {
        
                   }
               );
    
    
    
                InitializeComponent();
            }
    
            private void FormStrip_MouseLeave(object sender, EventArgs e)
            {
                BeginDoAction(UserAction.Leave, CurrentControl);
            }
    
            private void FormStrip_MouseEnter(object sender, EventArgs e)
            {
                BeginDoAction(UserAction.Enter , CurrentControl);
                
            }
        }
    }
    

  38. 卡索
    *.*.*.*
    链接

    卡索 2009-10-21 17:57:00

    @ winter-cn 真是毒手一个啊!不过不佩服不行,不学习也不行啊
    所以我还是先学习再佩服吧!

    想当年我学的电子信息工程的,丫丫的就没学习到数据结构、算法、编译原理、操作系统,人工智能貌似学习了,不过要是学习了的话现在也都给老师了。到是学习了一堆信息处理的,深刻记得信号系统以及疯狂的数学学习,从高数到概率到复变...

    现在想想要是我不写程序,直接去搞信号处理也不错吧!不过还是喜欢写程序,所以现在在继续学习数据结构、算法、编译原理、操作系统、人工智能这些课程啊!

    所以如果大家有好点的课件啥的给奉献些吧!spank218@163.com
    在此谢过啦!

  39. vczh[未注册用户]
    *.*.*.*
    链接

    vczh[未注册用户] 2009-10-21 18:35:00

    @Jeffrey Zhao
    直接写了,我也不想调试:
    当然我不知道是不是理解错,重复一下规则:
    group之间用--分割
    token之间用-分割
    token可以被单引号转义,字符串里面单引号用两个表示,于是有:

    simple_token = [^-]+
    complex_token = '([^']|'')+'
    token = simple_token|complex_token
    group = token(-token)*
    S = group(--group)*

    所以结论是
    (X(-X)*)(--(X(-X)*))*
    其中X=([^-]+|'([^']|'')+')
    所以组合起来的最终结果:

    (([^-]+|'([^']|'')+')(-([^-]+|'([^']|'')+'))*)(--(([^-]+|'([^']|'')+')(-([^-]+|'([^']|'')+'))*))*

  40. vczh[未注册用户]
    *.*.*.*
    链接

    vczh[未注册用户] 2009-10-21 18:38:00

    @JimLiu
    你可以这样理解嘛:
    /*开头;
    中间要么是[^*],要么是一串*后面不是/;
    一串*后/结尾
    所以结果自然就是:
    /\*([^*]|\*+[^/])*\*+/

  41. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-10-21 18:42:00

    vczh:
    @JimLiu
    你可以这样理解嘛:
    /*开头;
    中间要么是[^*],要么是一串*后面不是/;
    一串*后/结尾
    所以结果自然就是:
    /\*([^*]|\*+[^/])*\*+/





    //*
    abc
    */

    这个如何解析?

  42. vczh[未注册用户]
    *.*.*.*
    链接

    vczh[未注册用户] 2009-10-21 18:42:00

    我特喜欢玩字符串和编译器前端什么的,一直到现在都是,regex引擎都在重写第三次了,看见这道题目就无比兴奋啊。

    不过工作的时候是拖拖C#的控件……

  43. vczh[未注册用户]
    *.*.*.*
    链接

    vczh[未注册用户] 2009-10-21 18:44:00

    @Ivony...
    这明显就不是我规定的那种注释么,谈何解析

  44. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-10-21 18:47:00

    vczh:
    @Ivony...
    这明显就不是我规定的那种注释么,谈何解析




    在C++里面,那个abc可不是注释。。。。

    因为//*等于 // *,换言之/*的/与前/结合。


    C++的注释解析问题是一个“有名”的问题。

  45. vczh[未注册用户]
    *.*.*.*
    链接

    vczh[未注册用户] 2009-10-21 18:50:00

    @Ivony...
    非要做的话其实很容易的,另一种注释的正则表达式就是//[^\n]*(\n|$)嘛,两端一“|”不就成了么,当然写编译器的话就是另外一回事了,不过用正则表达式这样就差不多了。这里我忽略了一些可有可无的细节问题。

  46. 老赵
    admin
    链接

    老赵 2009-10-21 18:52:00

    @vczh
    你这不是浪费青春么,至少把你搞的东西写下来啊。

  47. vczh[未注册用户]
    *.*.*.*
    链接

    vczh[未注册用户] 2009-10-21 18:55:00

    你点我的名字不就看到了吗,我每次回帖都把我的博客的主页写上了,没人点才是浪费青春……http://www.cppblog.com/vczh

  48. vczh[未注册用户]
    *.*.*.*
    链接

    vczh[未注册用户] 2009-10-21 19:04:00

    @Jeffrey Zhao
    话说咱也在上海帮一个搞黑屏事件的公司打工,留个什么QQ啊MSN啊邮箱地址给咱纪念纪念……vczh@163.com

  49. 老赵
    admin
    链接

    老赵 2009-10-21 19:44:00

    @vczh
    牛淫呀

  50. JimLiu
    *.*.*.*
    链接

    JimLiu 2009-10-21 23:00:00

    @vczh
    你的/\*([^*]|\*+[^/])*\*+/
    我的/\*([^\*]|\**[^/\*])*\**\*/
    我的Regex解析器里*字符需要转义

    基本思路差不多

  51. JimLiu
    *.*.*.*
    链接

    JimLiu 2009-10-21 23:03:00

    @vczh
    //.*\n
    这是我的行注释,我的.是不包括换行符的。所以表述就比你那个轻松了。
    我做的Regex解析器并不标准。

  52. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-10-22 00:01:00

    vczh:
    @Jeffrey Zhao
    话说咱也在上海帮一个搞黑屏事件的公司打工,留个什么QQ啊MSN啊邮箱地址给咱纪念纪念……vczh@163.com


    挖 一个地儿打工的

  53. winter-cn
    *.*.*.*
    链接

    winter-cn 2009-10-22 00:13:00

    韦恩卑鄙:

    vczh:
    @Jeffrey Zhao
    话说咱也在上海帮一个搞黑屏事件的公司打工,留个什么QQ啊MSN啊邮箱地址给咱纪念纪念……vczh@163.com


    挖 一个地儿打工的


    一公司打工的 不过不是一地儿

  54. Duron800[未注册用户]
    *.*.*.*
    链接

    Duron800[未注册用户] 2009-10-22 11:32:00

    String的Aggregate是老赵自己扩展的?
    还是应该是char[]?

  55. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-10-22 11:48:00

    Cat Chen:
    @Jeffrey Zhao
    普通程序员里10里面有多少个是认真上过编译原理的呢……


    好多人甚至不是本专业的.

    当年我挂28门的时候 只有数据结构 操作系统和编译原理是过的....

  56. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-10-22 11:49:00

    Duron800:
    String的Aggregate是老赵自己扩展的?
    还是应该是char[]?


    char[]吧?

    貌似String 实现了 IEnumerable<Char>

  57. 老赵
    admin
    链接

    老赵 2009-10-22 11:51:00

    @韦恩卑鄙
    嗯嗯,和char[]无关,Aggregate是System.Linq.Enumerable里定义的扩展方法。

  58. 老赵
    admin
    链接

    老赵 2009-10-22 11:51:00

    @韦恩卑鄙
    猛男啊。

  59. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-10-22 11:55:00

    Jeffrey Zhao:
    @韦恩卑鄙
    猛男啊。


    因为在大学里面走吉日路线 出去赚钱..基本没上课 ..

  60. 老赵
    admin
    链接

    老赵 2009-10-22 12:13:00

    @韦恩卑鄙
    舒坦哪,我手头就从来没宽裕过……

  61. Duron800[未注册用户]
    *.*.*.*
    链接

    Duron800[未注册用户] 2009-10-22 12:34:00

    韦恩卑鄙:

    Duron800:
    String的Aggregate是老赵自己扩展的?
    还是应该是char[]?


    char[]吧?

    貌似String 实现了 IEnumerable<Char>


    是实现了,但是我在智能提示里找不到。

  62. 蛙蛙王子
    *.*.*.*
    链接

    蛙蛙王子 2009-12-12 22:31:00

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我