正则表达式解析RNS多项式无法捕获Modulus及系数分组问题

原始多项式示例 #

RNS Polynomial ([Modulus(68719403009), Modulus(68719230977), Modulus(137438822401)]): (67699591241,42814670386,92925202514)x^0 + (42539574637,55054036653,135659663247)x^1 + (52858091297,11618896202,6855552742)x^2 + (45970532823,20845087073,91272562929)x^3 + (11148839321,55275439733,5401722690)x^4 + (31959765643,40620395732,93052536121)x^5 + (57030732406,66026147059,6304524013)x^6 + (27778918692,11276356856,61606736382)x^7

现有正则的问题 #

你编写的正则\(\[(Modulus\(\d+\)(,*)\s*)+\]\):(\s*\((\d*,*)+\)x\^\d\s*\+*)+只能匹配整体结构，无法单独捕获分组的核心原因如下：

• 重复捕获分组被覆盖：你在捕获分组的外层直接加了量词+，比如(Modulus\(\d+\)(,*)\s*)+，这种写法下捕获分组只会保留最后一次匹配的结果，前面匹配到的多个Modulus、多个系数项都会被后续匹配内容覆盖，自然拿不到全部分组。
• 子匹配规则不严谨：\d*,*的写法允许空匹配，也没法准确匹配逗号分隔的多数字结构；x\^\d只能匹配指数为个位数的项，高次多项式会匹配失败。

修复方案 #

建议分两步匹配，先匹配整体结构，再单独提取分组：

1. 第一步匹配整体结构，分别捕获模数列表段和系数项列表段：

RNS Polynomial \(\[(?<modulus_list>Modulus\(\d+\)(?:,\s*Modulus\(\d+\))*)\]\):\s*(?<term_list>\(\d+(?:,\d+)*\)x\^\d+(?:\s*\+\s*\(\d+(?:,\d+)*\)x\^\d+)*)

2. 针对捕获到的modulus_list，用Modulus\((\d+)\)匹配提取所有模数的数值；针对捕获到的term_list，用\((?<coeffs>\d+(?:,\d+)*)\)x\^(?<exp>\d+)匹配提取每个项对应的系数组和指数值。

内容的提问来源于stack exchange，提问作者Rafaelo