소문자 화학 수식의 모든 가능한 순열 찾기

Question

소문자 화학 화학식의 모호성을 해결하려고합니다. 일부 요소 이름은 다른 요소 이름의 하위 문자열이므로 모두 함께 실행되므로 동일한 패턴에 대해 여러 개의 전역 일치가있을 수 있습니다.

hgas 문자열에 대한 정규식 /^((h)|(s)|(hg)|(ga)|(as))+$/을 고려하십시오. 두 가지 가능한 일치가 있습니다. hg, as 및 h, s, ga (입력과 비교하여 순서가 맞지만 문제는 아닙니다.) 모든 가능한 기호에 대한 정규식은 분명 더 길지만이 예제는 단순화를 위해 수행되었습니다.

Regex의 강력한 lookahead 및 lookbehind는 매우 긴 문자열조차도이 패턴과 일치하는지 또는 문자의 가능한 순열이 없는지를 결정할 수 있도록합니다. 부지런히 가능한 모든 순열을 시도합니다. 예를 들어, 나머지가 g 인 문자열의 끝에 도달하면 다시 돌아가 다른 조합을 다시 시도하십시오.

정규식 또는 확장명이 일종의 인 언어를 찾고 있는데,이 경우 일치 검색을 계속 수행하는 기능을 추가합니다.이 경우 과 hg, as을 찾습니다.

이 문제에 대한 regex의 복잡한 lookahead 및 lookbehind 기능을 재구성하는 것이 합리적인 해결책처럼 보이지 않습니다. 특히 최종 정규식에 각 기호 다음에 \ d *가 포함되어 있다고 생각하면 특히 그렇습니다.

추가 매핑을 찾으려면 /^((as)|(ga)|(hg)|(s)|(h))+$/ 정규 표현식의 순서를 뒤집을 생각이 있지만 대부분이 하나의 추가 일치를 찾을 것입니다. 정규 표현식에 이론적 배경이 없기 때문에 합리적인지 알아야합니다. 시험.

기존 정규 표현식을 사용하여 샘플 페이지를 만들었습니다.이 정규 표현식은 주어진 소문자 문자열에 대해 1 개 또는 0 개의 일치 항목을 찾아 대문자로 올바르게 반환합니다. 매칭시 첫 100 개의 화학 기호를 사용합니다.

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

TL; DR : I 문자열에 0 또는 1을 가능 화학식 순열 맞게 정규식있다. 1 개 이상의 경기를 찾으려면 어떻게해야합니까?

Answer 1

'독자에게 운동'을 떠날거야 (접근법에서와 같이), 그러나 나는 그것이 매우 흥미롭고 OP의 문제를 해결한다고 생각한다.

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. 

Answer 2

이 작업을 수행하는 일반 정규 표현식 라이브러리를 찾지 못한 이유는 모든 정규식으로이 작업을 수행 할 수 없기 때문입니다. 종료되지 않는 정규식이 있습니다.

방금 ​​용어 목록에 빈 문자열을 추가하여 예를 들어, 다음

'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', ...]) 

이 위의 지수 시간에 실행됩니다 그래서 동적 프로그래밍이가 기하 급수적으로 큰 문제가되지 않습니다 방법이있을 것입니다. 승리를 위해 Memoization.

주목할 가치가있는 마지막 것은 위 코드가 완전히 일치하는지 확인하지 않는다는 것입니다.

즉. 'hga'는 가능성으로 [ 'hg']를 반환 할 수 있습니다.

나는이 대답은 오프 주제 수 있습니다 잘 알고 있어요 실제 코딩, memrization, 그리고 내 PROFS 사랑스럽게 대답으로이 마지막 딸꾹질,

Answer 3

정규식을 사용하지 마십시오. 정규식은 말한대로 단 하나의 요소와 일치합니다. 대신 문자열의 모든 "의미"를 찾아야합니다. 각 요소의 아이폰에 1-2 문자라는 사실을 감안할 때, 나는이 algorythm (의사 코드를 용서)와 함께 가고 싶어요 :

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))if(checkSymbol(formula.substring(0,1))) false

다음, "h"

elements2 = [h] 

재귀 호출 마찬가지입니다 이 테스트 ga => 요소는 [h, ga, s] 진정한

elements2 = [h, ga] 

제 재귀 호출

시험 s, checksymbol true를 반환한다. 문자열의 길이는 0이므로 결과에 첫 번째 배열을 추가합니다 : [h, ga, s]

- 이의 첫 번째 단계

checkSymbol(formula.substring(0,2)가 "hg"가 요소뿐만 아니라 것을 발견 테스트의 두 번째 "지점"으로 돌아 가자

elements2 = [hg] 

그렇다면 우리 formulas([hg],"as")

"a" 대한 테스트가 실패

전화 (이것은 소자 없음) 및 테스트 F 또는 "as" 작품, 길이가 완전히 소모되어, 그 결과 [hg,as]이 algorythm는 O에서 최악의 경우 (N^2) 시간을 실행해야합니다 results[]

에 추가, n은 문자열의 길이되고 있습니다.

Answer 4

이것은 정규 표현식에 대한 작업이 아니므로 상태 시스템과 같은 것이 더 필요합니다.

문자열을 분석하여 알려진 모든 기호를 파싱하고,없는 경우 중지하고 계속하십시오. 한 문자열에서 전체 문자열이 사용되면 가능성을 발견했습니다. 같은

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"; 
?>