1

给定这两个字符串a = "/some/{tag}/here"，b = "/some/text/here"我想要一个有效的算法来验证是否b与定义的模式匹配，a以及是否提取b变量中的相应部分（即：）tag = "text"。

也欢迎使用 C 或 Go 实现，但伪代码也可以。

4

7 回答 7

3

阅读有关Knuth-Morris-Pratt 字符串搜索算法的信息。应该给你所有你需要的，包括伪代码。

于 2012-04-15T15:00:24.747 回答
2

也许你可以分开a

string[] array1 = a.Split('/');
string[] array2 = a.Split('/');
bool isEqual = (array1[2] == array2[2]);
于 2012-04-15T15:02:34.413 回答
2

许多好的正则表达式工具包可以做到这一点，但您可能必须更改模式的语法。例如，这是 Python 版本：

>>> import re
>>> a = re.compile("/some/(?P<pattern>.+)/here")
>>> b = "/some/text/here"
>>> a.match(b).group("pattern")
'text'
于 2012-04-15T15:00:31.107 回答
1

Go 回答：Go 标准库有一个URL 解析器和正则表达式包来帮助你。Go 不允许你在运行时命名变量，所以得到你的答案是tag = "text"没有意义的。相反，您可能希望将结果作为结构返回，或者可能在映射中收集多个结果。大纲可能类似于，

  1. 用大括号编译一个匹配你的标签语法的正则表达式。您在程序加载时执行一次。让我们称之为 tagRE。
  2. 将 tagRE 应用于模式“a”。此匹配的结果将是要匹配的 URL 部分以及标记的名称。（如果匹配失败，模式“a”无效。）
  3. 使用结果构造和编译另一个与真实 url 中的模式匹配的正则表达式。让我们称之为aRE。只要您认为将来可能需要匹配此模式，请坚持使用此正则表达式。重复编译它的工作是没有意义的。
  4. 可能根据需要对其他模式重复步骤 2 和 3，或者当模式对您的程序可用时。也许将这些收集在切片或地图或其他东西中。我猜您还希望将这些与您的应用程序中其他有用的东西相关联，例如找到匹配项时要执行的一些代码。
  5. 当你有一个你想要匹配的真实 url 时，你可能想先用 URL 包解析它以分离出 URL 路径。
  6. 将 aRE（或切片中的所有正则表达式）应用于路径并查看是否有匹配项。如果是这样，则返回一个结果，其中包含来自 a 的标记名称和匹配的路径部分。您可以通过创建结果结构或添加到结果映射来实现此目的。

显示正则表达式构造的代码：

package main

import (
    "fmt"
    "regexp"
)

var a = "/some/{tag}/here/{and}/there"
var aPath = `/some/bread/here/jam/there`

func main() {
    tagPat := regexp.MustCompile("([^{]*){([^}]+)}")
    aMatch := tagPat.FindAllStringSubmatch(a, -1)
    if aMatch == nil {
        fmt.Println("bad pattern")
        return
    }
    aRE := ""
    matchLen := 0
    for _, m := range aMatch {
        if m[1] > "" {
            aRE += `\Q` + m[1] + `\E`
        }
        aRE += "(?P<" + m[2] + ">.*)"
        matchLen += len(m[0])
    }
    if matchLen < len(a) {
        aRE += `\Q` + a[matchLen:] + `\E`
    }
    aPat := regexp.MustCompile(aRE)
    pathMatch := aPat.FindStringSubmatch(aPath)
    if pathMatch == nil {
        fmt.Println("url doesn't match")
        return
    }
    for tx, tag := range aPat.SubexpNames()[1:] {
        fmt.Println(tag, "=", pathMatch[tx+1])
    }
}

输出：

标签 = 面包
和 = 果酱

于 2012-04-15T16:58:06.937 回答
1

因此，您有一个格式为 的模式字符串/some/{tag}/here，并且您想确定其他字符串是否与该模式匹配。如果是这样，那么您要提取该{tag}部分。

在我看来，您可以将模式字符串分成三部分：

"/some/"
"{tag}"
"/here"

现在，使用标准 C 比较函数（我在想类似的东西strncmp），检查字符串是否以 . 开头"/some/"和结尾"/here"。如果是这样，那么您可以轻松找到标记字符串的开头和结尾。开头是：

stringBegin = s + strlen("/some/");
length = strlen(s) - strlen("/some/") - strlen("/here");

然后复制出那个子字符串就很简单了。

当然我的例子是使用常量字符串。但是，如果您可以轻松地拆分组件，那么您可以用变量替换常量。

于 2012-04-15T18:36:36.703 回答
0

我假设您的标签中不能有斜杠。如果不是这样，我的解决方案在没有大量修改的情况下将无法工作。

如果上述情况成立，那么您可以首先将您的路径标记为一个列表，如他的答案中显示的 user1288160。我的解决方案将在进行中。

path := strings.Split(url, "/")

然后您可以使用简单的状态机来处理令牌。

type urlParser func([]string) (urlParser, []string, error)

// define handlers for the various tokens that do appropriate things
var parseMap map[string]urlParser

var startParse = func(ps []string) (urlParser, []string, error) {
   switch  {
   case len(ps) == 0:
      return nil, nil, errors.New("End Of Path")
   case len(ps) == 1:
     return parseMap[ps[0]], nil, nil
   case len(ps) > 1:
     return parseMap[ps[0]], ps[1:], nil
   }
}

p := startParse
var err error
for {
   // get the next step in the state machine, unparsed portion of the path
   // and any errors.
   next, rst, pErr := p(path)
   // an error means we are done.
   if pErr != nil {
     break;
   }
   // set up for our next iteration of the parse loop.
   p = next
   path = rst
   err = pErr
}

您的 urlParsers 将是用您匹配的任何内容填充一些变量的闭包。

于 2012-04-16T16:16:37.880 回答
0

为了我们可以帮助它，我们需要背景信息。例如，什么构成了“模式”，数字？字母？数字和字母？允许使用哪些字符？

第一个风景：假设路径目标的位置是固定的，你可以这样做：

C代码：

char * string = "/some/text/here";
char * path;
char * b = "text";

if(strtok(strdup(string), "/")) {
    path = strtok(NULL, "/");
    if(!strcmp(b, path)) {
        /* Are equals. Do something.. */
    } else {
        /* ... */
    }
} else { 
    printf("Not found tag.\n");
}

第二景：

假设您只知道路径目标的前身，您可以执行以下操作：

C代码：

char * string = "/some/text/here";

char *cpath,            /* Current path */ 
     *ppath   = NULL,   /* Predecessor path */
     *ptpath  = "some", /* Predecessor path target */
     *pathcmp = "text"; /* Path to compare */ 

cpath = strtok(strdup(string), "/");

 while(cpath) { 
    ppath = cpath; 
    cpath = strtok(NULL, "/");

    if(ppath && ptpath && !strcmp(ppath, ptpath)) {
        if(!strcmp(cpath, pathcmp)) {
            /* Are equals. */
        } else {
            /* ... */
        }

        break;
    }
}

像这样的非常简单的情况，可以从正则表达式和 URI 解析中逃脱（当然，在良好的意义上）。

我希望这对你有帮助。

于 2012-05-08T00:02:40.283 回答