Shared 函数库

Appearance

testRegex ​

基于真实回溯算法的正则表达式匹配引擎，提供完整的算法可视化，帮助你理解正则引擎的工作原理。

快速示例

配置

匹配结果

状态
成功
匹配文本
42
位置
[14, 16]

算法可视化 - 回溯匹配过程

1 / 62
开始匹配
开始在文本 "The answer is 42" 中搜索模式 /\d+/
文本扫描
The·answer·is·42
▲
正则表达式
\d+
已匹配内容
(空)

使用说明

这是一个基于回溯算法的正则引擎可视化工具，展示真实的匹配过程：

  • 输入正则表达式和测试文本
  • 使用上一步/下一步按钮查看每一步的执行
  • 观察文本扫描位置和正则执行位置的变化
  • 理解回溯机制：当贪婪匹配失败时，引擎会减少匹配次数重试
  • 支持的特性：字面字符、转义字符 (\d \w \s)、字符集 [a-z]、量词 (+ * ? {n,m})

函数签名 ​

typescript
function testRegex(
  pattern: string,
  text: string
): RegexMatchResult

interface RegexMatchResult {
  /** 是否有匹配 */
  hasMatch: boolean
  /** 匹配的文本 */
  matchedText: string
  /** 匹配的起始位置 */
  matchIndex: number
  /** 匹配的结束位置 */
  matchEndIndex: number
  /** 可视化步骤 */
  steps: VisualizationStep[]
  /** 错误信息 */
  error?: string
}

interface VisualizationStep {
  /** 步骤编号 */
  stepNumber: number
  /** 文本位置 */
  textPos: number
  /** 正则位置 */
  patternPos: number
  /** 当前操作 */
  action: string
  /** 状态 */
  status: 'trying' | 'success' | 'fail' | 'backtrack'
  /** 已匹配的文本 */
  matched: string
  /** 说明 */
  explanation: string
  /** 当前检查的字符 */
  currentChar?: string
  /** 当前检查的正则片段 */
  currentPattern?: string
}

参数 ​

参数名类型必填说明
patternstring是正则表达式模式字符串
textstring是要匹配的文本

返回值 ​

类型说明
RegexMatchResult包含匹配结果、匹配位置和完整的算法执行步骤

工作原理 ​

基于回溯的正则引擎 ​

本函数实现了一个真实的正则表达式引擎，使用递归回溯算法：

  1. 逐位置尝试

    • 从文本的每个位置开始尝试匹配
    • 直到找到匹配或尝试完所有位置

  2. 递归匹配

    • 逐个匹配正则表达式的每个部分
    • 遇到量词时进行特殊处理

  3. 贪婪模式与回溯

    • 量词（+, *, ?）采用贪婪模式：先尽可能多地匹配
    • 如果后续匹配失败，回溯（减少匹配次数）重试
    • 直到找到成功的组合或完全失败

  4. 可视化记录

    • 记录每一步的操作
    • 包括尝试、成功、失败、回溯等状态
    • 显示当前文本位置、正则位置、已匹配内容

支持的正则特性 ​

  • ✅ 字面字符：a, b, 1, @ 等
  • ✅ 转义字符：\d (数字), \w (单词字符), \s (空白)
  • ✅ 字符集：[a-z], [0-9], [^abc]
  • ✅ 量词：
    • + 一次或多次
    • * 零次或多次
    • ? 零次或一次
    • {n,m} 指定次数范围
  • ✅ 回溯机制：贪婪匹配失败时自动回溯

使用示例 ​

基础匹配 ​

typescript
const result = testRegex('\\d+', 'Price: $42')
// result.hasMatch => true
// result.matchedText => "42"
// result.matchIndex => 8

可选字符 ​

typescript
// s 是可选的
const r1 = testRegex('https?', 'Visit https')
// => 匹配 "https"

const r2 = testRegex('https?', 'Visit http')
// => 匹配 "http"

零或多次 ​

typescript
// b 可以出现0次或多次
const r1 = testRegex('ab*c', 'ac')    // => 匹配 "ac"
const r2 = testRegex('ab*c', 'abc')   // => 匹配 "abc"
const r3 = testRegex('ab*c', 'abbc')  // => 匹配 "abbc"

查看匹配过程 ​

typescript
const result = testRegex('a+ab', 'aaab')

// 查看回溯步骤
result.steps
  .filter(s => s.status === 'backtrack')
  .forEach(s => console.log(s.explanation))
// => "量词贪婪匹配 3 次后续失败，回溯到 2 次重新尝试"

算法可视化 ​

在 Playground 中，你可以看到：

  1. 文本扫描

    • 显示当前扫描位置
    • 已扫描、当前、已匹配的字符用不同颜色标识

  2. 正则执行

    • 显示当前匹配到正则的哪个位置
    • 已完成和当前执行的部分

  3. 步进控制

    • 上一步/下一步查看每个操作
    • 观察回溯过程

  4. 状态说明

    • 每步的详细解释
    • 理解为什么匹配或不匹配

回溯机制示例 ​

对于模式 a+ab 匹配文本 aaab：

  1. a+ 贪婪匹配，匹配 3 个 a → aaa
  2. 尝试匹配后续的 ab，但文本只剩 b
  3. 匹配失败，回溯
  4. a+ 减少到 2 个 a → aa
  5. 尝试匹配 ab，文本剩余 ab
  6. 成功！最终匹配 aaab

这个过程在可视化中会清晰展示。

Copyright © 2023-present