在进行 Web 后端开发时，很重要的一个组件是 router。通常来说，后端的代码由许多 action 组成，router 的作用就是将发来的请求按照 URL 对应到相应的 action 上。
请求到达后端 Web 服务器时，已经不需要考虑域名和端口了，因此一个请求有如下形式：
“/{something_1}/{something_2}/.../{something_k}” 或 “/{something_1}/{something_2}/.../{something_k}?{parameter_list}”
其中 parameter_list 的组成为：“{name_1}={value_1}&{name_2}={value_2}&...&{name_n}={value_n}”。（第一种情况中的 parameter_list 为空）
例如 “/user/list/show?gender=male&birthyear=1990” 就是一个合法的请求，其中包含了两个参数 gender 和 birthyear，对应的 value 分别是 male 和 1990。
router 由许多条 path 组成，每一个 path 会对应到一个 action 上。router 在匹配 URL 到 path 时只看 parameter_list 之前的部分，例如之前的请求就只看 “/user/list/show” 这部分。parameter_list 内的参数会被直接送到 action 中。因此一个 path 总是具有如下形式：
“/{something_1}/{something_2}/.../{something_k}”
为了使得 router 更灵活，每一段中的 something 除了可以用具体的字符串外，还可以用一个正则表达式去匹配，并且提取出这部分的内容作为参数送到 action 去。这种情况下，something 的内容为“:{regexp_name}”，其中 regexp_name 对应一个正则表达式，会在后面给出具体的表达式。例如 router 中的一个 path 为 “/user/:handle/show”，其中“:handle” 对应了一个正则表达式，假设它可以匹配所有由小写英文字母组成的非空串。此时请求 “/user/testuser/show” 就能匹配这个 path，并且送往 action 多了一个 name 为 handle、value 为 testuser 的参数。再例如请求为 “/user/testuser/show?avatar=true&message=hello” 的话，不仅能匹配之前的 path，送到 action 的参数就会有三个：handle、avatar、message，对应的 value 分别为 testuser、true 和 hello。
但是使用带正则表达式的 path 时也受到一些限制。具体来说，如果有 router 中有两个 path，他们前面 i 个 something 段的内容完全相同（这 i 段里面可以含正则表达式项，此时就要求是名称相同的正则表达式），然后第 i+1 个 something 段的内容不同。下面分两种情况：
一个 path 这一段的内容是普通字符串，另一个 path 这一段的内容对应了正则表达式，那么这个正则表达式一定无法匹配前一个 path 第 i+1 段的字符串。例如一个 path 是 “/foo/:tmp/bar/pop”，另一个 path 是 “/foo/:tmp/:exp/push”，那么 exp 对应的正则表达式一定不会匹配 bar。
两个 path 这一段的内容都是正则表达式，那么这两个正则表达式匹配的字符串一定没有交集。例如一个 path 是 “/foo/:tmp/:aaa/push”，另一个 path 是 “/foo/:tmp/:bbb/pop”，那么不存在一个字符串能同时被 aaa 对应的正则表达式和 bbb 对应的正则表达式匹配。
最后介绍正则表达式。为了让情况简单一些，本题中的正则表达式规则相比于实际使用的有所简化。正则表达式的文法中有 Atom、Quantifier、Term、Alternative 这几个概念。用 Regexp 表示正则表达式，则每种概念具体为：
Regexp 可以由单个 Alternative 组成，或者由一个 Alternative 和一个 Regexp 组成，中间用字符 “|” 连接。对于前一种情况，该正则表达式匹配所有 Alternative 能匹配的东西。对于后一种情况，一个字符串要能被该正则表达式匹配，要么能被 “|” 前面的 Alternative 能匹配，要么能被 “|” 后面的 Regexp所匹配。
Alternative 由单个 Term 或多个 Term 连接组成，它能匹配这些 Term 所匹配的字符串的连接。换言之，一个字符串要被这个 Alternative 匹配，这个字符串能够拆成若干段（段数和 Alternative 的 Term 个数一样多），每段依次被 Alternative 的每个 Term 匹配。
Term 由一个 Atom 或一个 Atom 附带一个 Quantifier 组成。后面会了解到，Quantifier 对应了允许重复次数的区间。若 Term 由单个 Atom 组成，则 Term 能匹配的内容与 Atom 相同。如果 Atom 后带了 Quantifier，则如果一个字符串能划分为若干段（划分的段数在 Quantifier 指定的区间内），使得每段都能被 Atom 匹配，那么这个字符串就能被这个 Term 匹配。
Quantifier 的形式为 “{lower_bound,upper_bound}”，其中 lower_bound 和 upper_bound 各对应一个不超过 20 的非负整数，并且 upper_bound≥lower_bound，Quantifier 对应的区间为闭区间 [lower_bound,upper_bound]。注意 upper_bound 可以为空（此时中间的逗号还是有的），upper_bound 为空表示上界为无穷大。{1,3},{0,1},{2,2},{3,}均为合法的Quantifier，但 {3,2},{,1}就不合法。
Atom 有三种形式：第一种为单个字符，这里字符约定只能是英文字符（包括大写和小写）和数字，这种形式下的 Atom 所能匹配的内容就是该字符。第二种形式为字符区间，具体形式为 “[lower-upper]”，这里 lower 和 upper 各为单个字符，满足要么同时为小写英文字母、要么同时为大写字母、要么同时为数字，并且 lower 的ASCII码不小于 upper 的ASCII码，这种情况下的 Atom 所能匹配的内容就是这个区间内的字符（包括 lower 和 upper）。第三种形式是 “(Regexp)”，即一个合法的正则表达式套上一对括号，这种情况下该 Atom 能匹配的内容和括号内的正则表达式相同。
根据以上文法，“[0-9]{1,3}” 为合法的正则表达式，它能匹配长度为 1∼3 且由数字组成的字符串。“([a-z]|[0-9]){3,10}” 也为合法的正则表达式，它能匹配长度为 3∼10 且由小写英文字母和数字组成的字符串。更复杂的一个例子为 “01[0-1]{0,}|10[0-1]{0,}”，它能匹配所有 01 或 10 开头的 01 字符串。
