代码之家 › 专栏 › 技术社区 › MarkusQ

二维正则表达式有什么好的/有趣的类比吗?

graphics language-agnostic algorithm regex

MarkusQ · 技术社区 · 15 年前

二维正则表达式有什么好的(或者至少有趣但有缺陷的)类似物吗?

/aaac?(bc)*b?aaa/ 快速拉出一个交替的区域 b s和 c 它的边界至少有三个 a s也许同样重要的是,我可以在一个月后再来看看它在寻找什么。

我发现自己正在为2d中的类似问题编写自定义代码(有些问题要复杂得多/受限制得多),如果有一个更简洁、标准化的符号,那就好了,即使我必须自己编写它背后的引擎。

第二个示例可能称为“查找+”。目标是定位一个3个或更多的列 s、 a B 由3个或更多个括号括起 A. 她和三个或更多的人在一起在下面。它应该匹配:

..7...hkj.k f
7...a  h o j 
----a--------
 j .a,g- 8 9 
.aaabaaaaa7 j
 k .a,,g- h j
 hh a----?  j
    a   hjg

可以写成[b^(a{3})v(a{3})>(a{3})<(a{3})]或。。。

建议?

4 回复 | 直到 15 年前

MicSim 9 年前

我不是一个正则表达式专家,但发现这个问题很有趣,我环顾四周,发现这个问题很有趣 blog entry . 尤其是用于定义2D正则表达式的语法看起来很吸引人。链接在那里的报纸可能告诉你的比我多。

根据评论更新: 这里是到主要作者页面的链接,您可以在这里下载链接的论文 “二维语言” : http://www.mat.uniroma2.it/~giammarr/Research/pubbl.html

NVRAM 15 年前

好问题。

长方形 属于 [bc] a 边界 A. [c([bc]*a})v([bc]*a)>([bc]*a)<([bc]*a)] (在您的语法中)

xxxaaaaaxxx
yzyabcba12d
defabcbass3
oreabcba3s3
s33aaaaas33
k388x.egiee

如果您可以将其约束为“+”,那么您的任务就容易多了。正如ShuggyCoUk所说,解析RE通常相当于DFSM——但对于单个串行输入,这大大简化了事情。

在“RE+”引擎中,不仅要调试引擎,还要调试输入表达式的每个位置。我希望编译器能够捕获它可能出现的任何错误。考虑到这一点,您还可以使用明确的四个RE,例如:

REPlus engine = new REPlus('b').North("a{3}")
   .East("a{3}").South("a{3}").West("a{3}");

但是,根据您的实现情况,这可能会很麻烦。

至于遍历引擎——北/西模式匹配RtL还是LtR?如果模式与贪婪子匹配或不与贪婪子匹配有不同的匹配,这可能很重要。

顺便提一下,我认为您的示例中的“^”应该是括号外左侧的一个字符。

Rob Lachlan 15 年前

正则表达式设计用于在一维中对模式进行建模。据我所知,您希望在二维字符数组中匹配模式。

你会用正则表达式吗?这取决于您正在搜索的属性是否可分解为可在一维中匹配的组件。如果是这样,您可以在列和行上运行正则表达式,并从这些列和行中查找解决方案集中的交点。根据您遇到的特定问题,这可能会解决问题,也可能会在二维阵列中找到可能是解决方案的区域。

无论您的问题是否可分解,我认为编写一些自定义代码将是不可避免的。但至少这听起来是个有趣的问题,所以工作应该是愉快的。

SmacL 15 年前

你本质上是在说一个 spatial query language . 如果您查找空间查询、地理查询和图形查询,就会发现很多。空间部分通常归结为区域中具有其他给定属性的点、线和对象。区域可以指定为多边形、与点的距离(例如圆)、与线性要素(例如道路)的距离、线性要素一侧的所有点等。。。然后,您可以进入更复杂的查询,如所有最近邻集、最短路径、旅行商,以及Delaunay TINs和Voronoi图等细分关系。