3

我正在尝试解决小写化学式中的歧义。由于某些元素名称是其他元素名称的子字符串，并且它们都一起运行，因此同一模式可以有多个全局匹配。

考虑/^((h)|(s)|(hg)|(ga)|(as))+$/针对字符串的正则表达式hgas。有两种可能的匹配。hg, as和h, s, ga（与输入相比无序，但不是问题）。显然，所有可能符号的正则表达式会更长，但这个例子是为了简单起见。

正则表达式强大的前瞻和后瞻功能使其能够最终确定即使是很长的字符串是否与此模式匹配，或者是否有可能的字母排列。它将努力尝试所有可能的匹配排列，例如，如果它以 leftover 命中字符串的末尾，则g返回并重试不同的组合。

我正在寻找一个正则表达式，或者一种具有某种扩展名的语言，它增加了在找到匹配项后继续查找匹配项的能力，在这种情况下，查找h, s, ga以及hg, as.

为这个问题重建复杂的正则表达式的前瞻和后视功能似乎不是一个合理的解决方案，特别是考虑到最终的正则表达式还在每个符号后包含一个 \d*。

我想过颠倒正则表达式的顺序/^((as)|(ga)|(hg)|(s)|(h))+$/，以找到额外的映射，但最多只能找到一个额外的匹配项，而且我没有正则表达式的理论背景，不知道尝试是否合理。

我使用现有的正则表达式创建了一个示例页面，它为给定的小写字符串找到 1 个或 0 个匹配项，并将其正确大写（并且无序）返回。它在匹配中使用前 100 个化学符号。

http://www.ptable.com/Script/lowercase_formula.php?formula=hgas

tl; dr：我有一个正则表达式来匹配字符串中的 0 或 1 个可能的化学式排列。如何找到超过 1 个匹配项？

4

4 回答 4

3

我很清楚这个答案可能是题外话（如方法），但我认为它很有趣，它解决了 OP 的问题。

如果您不介意学习一门新语言（Prolog），那么它可能会帮助您生成所有可能的组合：

name(X) :- member(X, ['h', 's', 'hg', 'ga', 'as']).

parse_([], []).
parse_(InList, [HeadAtom | OutTail]) :-
    atom_chars(InAtom, InList),
    name(HeadAtom),
    atom_concat(HeadAtom, TailAtom, InAtom),
    atom_chars(TailAtom, TailList),
    parse_(TailList, OutTail).

parse(In, Out) :- atom_chars(In, List), parse_(List, Out).

样品运行：

?- parse('hgas', Out).
Out = [h, ga, s] ;
Out = [hg, as] ;
false.

改进后的版本，包括对数字的处理，稍微长一点：

isName(X) :- member(X, ['h', 's', 'hg', 'ga', 'as', 'o', 'c']).

% Collect all numbers, since it will not be part of element name.
collect([],[],[]).
collect([H|T], [], [H|T]) :-
    \+ char_type(H, digit), !.
collect([H|T], [H|OT], L) :-
    char_type(H, digit), !, collect(T, OT, L).

parse_([], []).
parse_(InputChars, [Token | RestTokens]) :-
    atom_chars(InputAtom, InputChars),
    isName(Token),
    atom_concat(Token, TailAtom, InputAtom),
    atom_chars(TailAtom, TailChars),
    parse_(TailChars, RestTokens).

parse_(InputChars, [Token | RestTokens]) :-
    InputChars = [H|_], char_type(H, digit),
    collect(InputChars, NumberChars, TailChars),
    atom_chars(Token, NumberChars),
    parse_(TailChars, RestTokens).

parse(In, Out) :- atom_chars(In, List), parse_(List, Out).

样品运行：

?- parse('hgassc20h245o', X).
X = [h, ga, s, s, c, '20', h, '245', o] ;
X = [hg, as, s, c, '20', h, '245', o] ;
false.

?- parse('h2so4', X).
X = [h, '2', s, o, '4'] ;
false.

?- parse('hgas', X).
X = [h, ga, s] ;
X = [hg, as] ;
false.
于 2012-09-19T20:08:28.463 回答
1

您没有找到执行此操作的通用正则表达式库的原因是所有正则表达式都无法执行此操作。有些正则表达式不会终止。

想象一下您的示例，您刚刚将空字符串添加到术语列表中，然后

'hgas' 可能是：

['hg', 'as']
['hg', '', 'as']
['hg', '', '', 'as']

你可能只需要自己动手。

在伪代码中：

def findall(term, possible):
    out = []

    # for all the terms
    for pos in possible:

        # if it is a candidate
        if term.startswith(pos):

            # combine it with all possible endings
            for combo in findall(term.removefrombegining(pos), possible):
                newCombo = combo.prepend(out)
                out.append(newCombo)
    return out


findall('hgas', ['h', 'as', ...])

以上将在指数时间内运行，因此动态编程将成为这不是指数大问题的方式。为了胜利而记忆。

最后值得注意的是上面的代码没有检查它是否完全匹配。

IE。'hga' 可能会返回 ['hg']。

正如我的教授们亲切地说的那样，我将把实际的编码、记忆和最后的小插曲留给“读者练习”

于 2012-09-19T19:44:37.200 回答
0

不要使用正则表达式。正如您所说，正则表达式仅匹配 1 个元素，相反，您需要找到字符串的所有可能“含义”。鉴于每个元素的长度是 1-2 个字符，我会使用这个算法（原谅伪代码）：

string[][] results;



void formulas(string[] elements, string formula){
    string[] elements2=elements;


    if(checkSymbol(formula.substring(0,1))){
        elements.append(formula.substring(0,1));
        if(formula.length-1 ==0){
            results.append(elements);
        } else {
            formulas(elements,formula.substring(1,formula.length);
        }
    }
    if(checkSymbol(formula.substring(0,2))){
        elements2.append(formula.substring(0,2));
        if(formula.length-2 ==0){
            results.append(elements2);
        } else {
            formulas(elements2,formula.substring(2,formula.length);
        }
    }


}

bool checkSymbol(string symbol){
    // verifies if symbol is the name of an element
}

输入"hgas"（让我们先深入）

第一步： checkSymbol(formula.substring(0,1))为真"h"

elements2 = [h]

递归调用，if(checkSymbol(formula.substring(0,1))) false

然后它测试ga=> true

elements2 = [h, ga]

第三次递归调用

测试s，checksymbol返回 true，元素是 then [h, ga, s]。子字符串的长度为 0，因此它附加到第一个数组的结果中：[h, ga, s]

——让我们回到第一步的第二个“分支”

测试checkSymbol(formula.substring(0,2)发现它"hg"也是一个元素

elements2 = [hg]

然后我们调用formulas([hg],"as")

测试"a"失败（它不是元素）和测试"as"工作，长度完全消耗，结果[hg,as]附加到results[]

在最坏的情况下，这个算法应该在 O(n^2) 时间内运行，n 是字符串的长度。

于 2012-09-19T20:18:47.423 回答
0

这不是正则表达式的工作，您需要更像状态机的东西。

您需要解析弹出所有已知符号的字符串，如果没有则停止，然后继续。如果整个字符串在一个分支上被消耗掉，你就发现了一种可能性。

在 PHP 中，类似：

<?php
    $Elements = array('h','he','li','s','ga','hg','as',
         // "...and there may be many others, but they haven't been discovered".
    );

    function check($string, $found = array(), $path = '')
    {
        GLOBAL $Elements, $calls;
        $calls++;
        if ('' == $string)
        {
            if (!empty($path))
                $found[] = $path;
            return $found;
        }
        $es = array_unique(array(
                  substr($string, 0, 1), // Element of 1 letter ("H")
                  substr($string, 0, 2), // Element of 2 letter ("He")
        ));
        foreach($es as $e)
            if (in_array($e, $Elements))
                    $found  = check(substr($string, strlen($e)), $found, $path.$e.',');
        return $found;
    }

    print_r(check('hgas'));
    print "in $calls calls.\n";
?>
于 2012-09-19T20:32:31.047 回答