问题来源
要处理的问题
回溯的优化
编码

1. 问题来源

这个问题，是看到有人提到带中文数字的章节标题，要排序的问题引起的。比如对于：

title_list = [
'第一章',
'第三章',
'第五章',
'第四章',
'第二章',
]

想“正确”排序的话，你直接 title_list.sort() 是不行地：

zys@tower:~$ python3
Python 3.7.1 (default, Apr  1 2019, 01:01:48) 
[GCC 7.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> title_list = [
... '第一章',
... '第三章',
... '第五章',
... '第四章',
... '第二章',
... ]
>>> title_list.sort()
>>> title_list
['第一章', '第三章', '第二章', '第五章', '第四章']
>>>

原因是在具体编码的码表中，“三”并不一定排在“二”前面，码表的编撰可不会特别考虑中文的排序这种事。

当然，对于不同的编码，这几个数字字符的相对位置，可能会有差异。上面的例子，只代表 Unicode 的一个结果。你转成 GB18030 或者 BIG5 的字节，结果可能不同。但这也足够说明，中文的数字依赖字典序是不可靠的。编码不同，结果就不同，这里的“字典序”本身就没有标准可言，如果你假设 Unicode ，那事实上这些字符的顺序也不是我们希望的“1 2 3 4”这样的顺序。

所以，这里就引出，我们可以把中文数字，转成阿拉伯数字，然后使用整数大小来排序就可以准确控制了。

光是 “一”，“二”，“三” 这些单个数字，倒是好办，我们写死一位数的映射都可以解决问题。接下来要说的，自然是更一般性的处理方法。

比如：

一千零一亿一千零一万一千零一

2. 要处理的问题

看上面的中文数字，直观地，可以看出中文数字其实是由“数字”和“单位”构成的：

数字就是“一”，“二”，“三”这些。
单位则是“千”，“万”，“亿”。

这里我们先明确一下“十”这个“搅屎棍”的位置，它到底算数字，还是算单位。从我们日常习惯用法中看，它是两者都有的：

用于单位，“一十”，“一十五万”。
用于数字，“一千零十万”。（注意区分，“一千”个“十万”，和“一千零十”个“万”的不同）

我们会把“十”作为单位处理，把它当数字时的情况作为特例。这样面对的特例，要比作为数字少得多。

如果我们能正确解析出汉字数字中的“数字”与“单位”的话，那么通过映射与简单运算，就可以得到需要的阿拉伯数字结果。

比如对于：

一千零一亿一千零一万一千零一

如果我们可以解析到：

1001
亿
1001
万
1001

那最后的结果就很容易了，是 1001 * 10^8 + 1001 * 10^4 + 1001。

实际的问题当然没这么简单，上面的结果没问题，但首先你要能得到 1001 啊：

1
- 千
- 零
- 1
亿
1
- 千
- 零
- 1
万
1
- 千
- 零
- 1

这才是我们从文字中看到的状况。

上面的结构，像是一颗树，按这个方向，为了方便定义节点和分支，我们可以整理得到：

亿
- 1
- 千
- 零
- 1
万
- 1
- 千
- 零
- 1
1
- 1
- 千
- 零
- 1

继续分解：

亿
- 千
  - 1
- 零
- 1
万
- 千
  - 1
- 零
- 1
1
- 千
  - 1
- 零
- 1

对于这个结构，针对每一个节点，我们从下往上的顺序计算，就可以计算出每个节点的值——平行节点的值相加，父子节点的值相乘，过而得到最终值。再推广一下，整颗树从下往上顺序遍历就可以算出结果。

上面的分拆过程，有助于我们看到这个问题更深的一些信息，这些信息就是我们设计代码的参考。

我们的分拆，在思维上最开始可能是依据结果的倒推（我们知道“一千零一亿一千零一万一千零一”就是 1001 * 10^8 + 1001 * 10^4 + 1001），但我们写代码需要的是正向的逻辑，所以回到最初，去找出我们直觉上的逻辑依据：

对于：

一千零一亿一千零一万一千零一

我们怎么发现中间这些字应该提出来作为子节点？

一千零一亿一千零一万一千零一

这个问题不难。

前面介绍了“数字”和“单位”的概念，我们把原始汉字中这两者分开：

一千零一亿一千零一万一千零一

只看标色的“单位”，单位的值我们可以以 10 的指数来表示，从左右到绘制到直角坐标系上就是：

从图上可以看出，我们要提出来的节点，正好是“波峰”。

再找个例子看看：

一千一百万零十一亿一千一百一十一万一千一百一十一

中文的习惯，报数是从大单位到小单位报，所以单位的连线应该是一直向下的。而突然向上，出现波峰，那么肯定是某个大单位的阶段性结束，前面说的那些都是为了“修辞”这个大单位的。

比如上图的，一千一百，单位是变小的，但马上接了一个万，至此，“万”这个范围，就结束了。

接着万，后面是十，这是一个缩小的单位，没有特殊，再来就是亿，它是一个比“万”大的单位，同理，意味着“亿”这个范围结束了。

后面还有一个极点，在万上，也是同样的道理。

再往上看一层，整个过程，波峰处的单位顺序是万 - 亿 - 万。

这是否意味着子节点是这三个呢？

万
- x
- x
亿
- x
- x
万
- x
- x

答案是否定的，“万亿”，是“万” x “亿”，不是“万” + “亿”。

所以正确的结构应该是：

亿
- x
- x
- 万
  - x
  - x
万
- x
- x

从万 - 亿 - 万要得到这样的结构，又有什么规则？

回溯。

如果从左往右扫，即当碰到一个更大的单位时，需要回溯之前的节点，之前所有不比它大的单位，都应该成为其子节点。

到此，一般性的规则就介绍完了。（其实就这么点）

运用这个规则，就可以把中文数字，转成一个树结构，进而运算出阿拉伯数字结果。

3. 回溯的优化

这点算是经验之谈吧。

当一个场景，如果你从左到右遍历，需要回溯处理。那么换个方向，从右到左遍历，可能就不需要回溯了。如果遍历对象长度很大，这通常会带来可观的性能提升，及代码编写上的简单。

看之前示例的图和树结果：

亿
- x
- x
- 万
  - x
  - x
万
- x
- x
x
x
x

从左到右遍历之所以要回溯，是因为相对于这个树结构，从左到右遍历的过程是后找到父节点的。当你确定了一个父节点之后，它的子节点你需要重新组织调整。

如果我们把方向反过来，从右到左遍历的话，对于这个树，总是先遇到父节点。需要做的判断，仅仅是当前节点是否结束，然后开始一个新的父节点，并不需要不断折返来调整节点结构。

新节点开始的规则也简单明了，就是碰到了一个比之前都大的单位。

这些规则弄明白之后，编码就相对容易了。剩下的更多时间，是处理各种不合逻辑的例外情况，毕竟，人说话是依赖“习惯”，而不是“逻辑”。

4. 编码

4.1. 基本配置准备

就是数字和单位的映射，一些信息可以从网上搜索到：

num_map = {
    u'零': 0,
    u'〇': 0,
    u'两': 2,
    u'一': 1, u'二': 2, u'三': 3, u'四': 4, u'五': 5, u'六': 6, u'七': 7, u'八': 8, u'九': 9,
    u'壹': 1, u'贰': 2, u'叁': 3, u'肆': 4, u'伍': 5, u'陆': 6, u'柒': 7, u'捌': 8, u'玖': 9,
    u'廿': 20,
    u'卅': 30,
    u'卌': 40,
    u'圩': 50,
    u'圆': 60,
    u'进': 70,
    u'枯': 80,
    u'枠': 90,
}
rank_map = {
    u'十': 10, u'百': 100, u'千': 1000, u'万': 10000, u'亿': 100000000,
    u'拾': 10, u'佰': 100, u'仟': 1000,
    u'兆': 10 ** 16
}

后面如果找到新的词，也可以直接添加进去。

4.2. 解析中文

这一步做的事，是把原始中文字符转换成我们好处理的，中间状态的数据结构：

先用比较直接简单的例子来随时测试我们代码的基本功能，如： 四千五百万八千零一 。

简单地使用一个 dict ，有 type 和 value 两个值就好。

设计上，一点技巧，一是把 0 单独处理，因为其实我们知道零有些特殊，但还没有事例来说明它到底特殊在哪里，所以，给它一点特殊待遇，专门设计一个 zero 的类型。

另一个，是在最后添加一个 complete 类型。这个明确的收尾信息，可以方便我们处理一些兜底工作，有助于更好的代码结构。（这个场景，类似于在一个迭代过程中，有一个临时容器。当迭代结束后，因为在迭代里面的代码并不知道迭代何时结束，所以一般你需要在迭代外再额外处理一下这个临时容器。如果在迭代过程中有一个明确的结束信号，比如明确知道这是最后一个条目了，那么在迭代内部就可以完成所有工作，代码会好看点。）

s = '四千五百万八千零一'

def parse(s):

    gen = []

    for c in s:
        if c in num_map:
            if num_map[c] == 0:
                gen.append({'type': 'zero'})
            else:
                gen.append({'type': 'number', 'value': num_map[c]})

        if c in rank_map:
            gen.append({'type': 'rank', 'value': rank_map[c]})

    gen.append({'type': 'complete'})
    return gen

执行 parse 可以得到这样的结果：

[
    {'type': 'number', 'value': 4},
    {'type': 'rank', 'value': 1000},
    {'type': 'number', 'value': 5},
    {'type': 'rank', 'value': 100},
    {'type': 'rank', 'value': 10000},
    {'type': 'number', 'value': 8},
    {'type': 'rank', 'value': 1000},
    {'type': 'zero'},
    {'type': 'number', 'value': 1},
    {'type': 'complete'}
]

对于理想状态，这个结果足够我们进行接下来的工作了。

4.3. 生成阿拉伯数字

这一步的一个正常过程，就是前面我们讲“规则”的过程。先做一个从左到右的正向遍历，不加回溯，处理一些最简单场景。接着加入更多场景，发现不加回溯搞不定。最后想到，换个方面遍历更直接方便。

项目上的代码并不是一蹴而就的，中间会经历很多次的重构。

这里就直接给出反向遍历的一个简单结果：

def generate(token_list):

    gen = token_list[:-1]
    gen.reverse()
    gen.append(token_list[-1])

    block = []
    level_rank = 1
    current_rank = 1
    for o in gen:

        if o['type'] == 'number':
            if not block:
                block.append([])
            block[-1].append(o['value'] * current_rank)

        if o['type'] == 'rank':
            rank = o['value']

            if not block:
                level_rank = rank
                current_rank = rank
                block.append([])
                continue

            if rank > level_rank:
                level_rank = rank
                current_rank = rank
                block[-1] = sum(block[-1])
                block.append([])
            else:
                current_rank = rank * level_rank
                block[-1] = sum(block[-1])
                block.append([])

        if o['type'] == 'zero':
            continue

        if (o['type'] == 'complete'):
            if isinstance(block[-1], list):
                block[-1] = sum(block[-1])

    return sum(block)

token_list 先作了 reverse 。
遍历过程中，小心处理 number 值和 rank 值就好。（这点可能需要反复调试和思考）

最终，这个 generate 就可以得到我们期望的结果， 45008001 。

不错的开始。

前面一直在提“理想状况”，是我们的代码只是针对 45008001 这一个普通例子完成。接下来，像这种业务场景，我们就可以做很多的测试用例，然后来“测试驱动完善”了。

4.4. 更多测试用例

下面的测试用例，绝大部分，是从： https://github.com/HaveTwoBrush/cn2an/blob/master/cn2an/cn2an_test.py 这里获取的。

TEST_SUIT = {
    u"一": 1,
    u"两": 2,
    u"十": 10,
    u"十一": 11,
    u"一十一": 11,
    u"一百一十一": 111,
    u"一千一百一十一": 1111,
    u"一万一千一百一十一": 11111,
    u"一十一万一千一百一十一": 111111,
    u"一百一十一万一千一百一十一": 1111111,
    u"一千一百一十一万一千一百一十一": 11111111,
    u"一亿一千一百一十一万一千一百一十一": 111111111,
    u"一十一亿一千一百一十一万一千一百一十一": 1111111111,
    u"一百一十一亿一千一百一十一万一千一百一十一": 11111111111,
    u"一千一百一十一亿一千一百一十一万一千一百一十一": 111111111111,
    u"壹": 1,
    u"拾": 10,
    u"拾壹": 11,
    u"壹拾壹": 11,
    u"壹佰壹拾壹": 111,
    u"壹仟壹佰壹拾壹": 1111,
    u"壹万壹仟壹佰壹拾壹": 11111,
    u"壹拾壹万壹仟壹佰壹拾壹": 111111,
    u"壹佰壹拾壹万壹仟壹佰壹拾壹": 1111111,
    u"壹仟壹佰壹拾壹万壹仟壹佰壹拾壹": 11111111,
    u"壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹": 111111111,
    u"壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹": 1111111111,
    u"壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹": 11111111111,
    u"壹仟壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹": 111111111111,
    u"一百零一": 101,
    u"一千零一": 1001,
    u"一千零一十一": 1011,
    u"一千一百零一": 1101,
    u"一万零一": 10001,
    u"一万零一十一": 10011,
    u"一万零一百一十一": 10111,
    u"一十万零一": 100001,
    u"一百万零一": 1000001,
    u"一千万零一": 10000001,
    u"一千零一万一千零一": 10011001,
    u"一千零一万零一": 10010001,
    u"一亿零一": 100000001,
    u"一十亿零一": 1000000001,
    u"一百亿零一": 10000000001,
    u"一千零一亿一千零一万一千零一": 100110011001,
    u"一千亿一千万一千零一": 100010001001,
    u"一千亿零一": 100000000001,

    u"十万": 100000,
    u"十万零一": 100001,
    u"十亿零一万零一": 1000010001,

    u"拾万零壹": 100001,
    u"拾亿零壹万零壹": 1000010001,

    u'一千一': 1100,
    u'一千一零一': 1101,
    u'一千零十亿': 101000000000,
    u'一一': 11,
    u'一二三': 123,
}

拿着这些测试用例去验证 parse 和 generate 肯定会发现很多异常的，错误的情况。再针对这些错误的用例，去补充，修改代码就好。语言不是数学，追求系统层面的完备我觉得没必要，特殊情况一个 if 就行，实在不行，就再加一个 if 。

4.5. 完整实现

下面是一个我多次修改后的一个相对完整的实现，已经通过上面列出的所有测试。

# -*- coding: utf-8 -*-


num_map = {
    u'零': 0,
    u'〇': 0,
    u'两': 2,
    u'一': 1, u'二': 2, u'三': 3, u'四': 4, u'五': 5, u'六': 6, u'七': 7, u'八': 8, u'九': 9,
    u'壹': 1, u'贰': 2, u'叁': 3, u'肆': 4, u'伍': 5, u'陆': 6, u'柒': 7, u'捌': 8, u'玖': 9,
    u'廿': 20,
    u'卅': 30,
    u'卌': 40,
    u'圩': 50,
    u'圆': 60,
    u'进': 70,
    u'枯': 80,
    u'枠': 90,
}
rank_map = {
    u'十': 10, u'百': 100, u'千': 1000, u'万': 10000, u'亿': 100000000,
    u'拾': 10, u'佰': 100, u'仟': 1000,
    u'兆': 10 ** 16
}


s = u'一兆零一'


def convert(s):
    gen = []
    last_rank = 1

    #十 起头,其它 rank 起头, 都要补一,否则后面逻辑无法统一解释
    if s[0] in rank_map:
        gen.append({'type': 'number', 'value': 1})

    for c in s:
        if c in num_map:
            if num_map[c] == 0:
                #前面是数字,要补 rank , 1101
                if gen[-1]['type'] == 'number':
                    gen.append({'type': 'rank', 'value': int(last_rank / 10)})

                gen.append({'type': 'zero'})
            else:
                #连着两个数字, 如 一一
                if gen and (gen[-1]['type'] == 'number'):
                    gen.append({'type': 'rank', 'value': 10})
                gen.append({'type': 'number', 'value': num_map[c]})

        if c in rank_map:

            # 连续两个 rank ,合并
            # 十 有歧义,如果它前面带零不能合,如 一千零十亿, 还要把它改成数字
            # 不带零要合, 如 一十万零一
            last_rank = rank_map[c]
            if gen and gen[-1]['type'] == 'rank':
                if (len(gen) > 1) and (gen[-1]['value'] == 10) and (gen[-2]['type'] == 'zero'):
                    gen[-1]['type'] = 'number'
                    gen.append({'type': 'rank', 'value': rank_map[c]})
                else:
                    gen[-1]['value'] *= rank_map[c]
                continue

            gen.append({'type': 'rank', 'value': rank_map[c]})

    #补末位的省略, 如 一千一
    if gen and len(gen) > 1:
        if (gen[-1]['type'] == 'number') and (gen[-2]['type'] == 'rank'):
            gen.append({'type': 'rank', 'value': int(gen[-2]['value'] / 10)})

    gen.reverse()
    gen.append({'type': 'complete'})

    block = []
    level_rank = 1
    current_rank = 1
    for o in gen:

        if o['type'] == 'number':
            if not block:
                block.append([])
            block[-1].append(o['value'] * current_rank)

        if o['type'] == 'rank':
            rank = o['value']

            if not block:
                level_rank = rank
                current_rank = rank
                block.append([])
                continue

            if rank > level_rank:
                level_rank = rank
                current_rank = rank
                block[-1] = sum(block[-1])
                block.append([])
            else:
                current_rank = rank * level_rank
                block[-1] = sum(block[-1])
                block.append([])

        if o['type'] == 'zero':
            continue

        if (o['type'] == 'complete'):
            if isinstance(block[-1], list):
                block[-1] = sum(block[-1])

    return sum(block)


if __name__ == '__main__':
    print(s, convert(s))


# from: https://github.com/HaveTwoBrush/cn2an/blob/master/cn2an/cn2an_test.py

TEST_SUIT = {
    u"一": 1,
    u"两": 2,

    ...

    u'一千一': 1100,
    u'一千一零一': 1101,
    u'一千零十亿': 101000000000,
    u'一一': 11,
    u'一二三': 123,
}

count = 0
error = 0
for c, v in TEST_SUIT.items():
    r = convert(c)
    count += 1
    if v != r:
        error += 1
        print('ERROR', c, v, r)

print('SUM: {} ERROR: {}'.format(count, error))

汉字数字转阿拉伯数字

1. 问题来源

2. 要处理的问题

3. 回溯的优化

4. 编码

4.1. 基本配置准备

4.2. 解析中文

4.3. 生成阿拉伯数字

4.4. 更多测试用例

4.5. 完整实现