3

それで、

問題の解決策を探しています-整数間隔を正規表現に変換する方法。2 つの数値があるAとしBます。どちらも正の整数であり、A < B

今、私はアルゴリズム（コードかもしれません）を探しています。これは単一の正規表現になり、AとB（境界線を含む）の間の数字と一致します。たとえば、私はA=20,を持っています。B=35正しい正規表現は^2[0-9]$|^3[0-5]$- です。20..35 の数字だけがそれに適合するからです。

一般的なケースでは、Aが 83724Bのようなもので、 28543485 のようなものがいつなのかは、それほど明白ではありません。

更新。ほとんどの場合、それは好奇心の問題です。私はこれを行う最善の方法を知っています: 結果を返す:A<=X && X<=B

4

3 に答える 3

4

この状況で正規表現を使用する理由

私はこれを行うだけです：

boolean isBetween = num > A && num < B;

(Javaで書かれたコード)

はるかに簡単に、あなたが求めているような正規表現は巨大になる可能性があり、この状況でそれを使用することは無意味で非効率的です.

幸運を。

このタスクでどうしても RegEx を使用したい場合は、この Web サイトを参照し、詳細モードをオンにして正規表現を実行すると、作成者の RegEx がどのように機能するかが説明されます。

于 2013-08-22T07:39:13.137 に答える
2

他の人がすでに言っているように、これはあまり良い考えではありません。すべての整数を照合して後でフィルタリングするよりも高速ではありません。しかし、とにかくあなたの質問に答えます。

間隔の大きさに応じて、正規表現エンジンに最適化させることができるので、 - で区切られた|値のリストを出力するだけです。これは、有限オートマトン理論の基本アルゴリズムを使用してアルゴリズム的に最小化できます。

これは、間隔が長い場合、メモリを大量に消費する可能性があります。その場合、A と B の異なる長さのすべての数字を一度に一致させることができます。あなたの例では、6〜7桁のすべての数字が簡単に一致し[0-9][1-9]{5,6}ます。これで、再帰的に作成できる境界ケースが残っています (この場合の A 側については、再帰の基本ケースは含めていません)。

  1. S を A とする。
  2. f を S の 1 桁目とg=f+1し、n を(digits of S)-1
  3. 次の f より大きい数字の正規表現にセグメントを追加します。[g-9][0-9]{n}
  4. f で始まる数字のセグメントを追加します。f(recursive call starting from step 2, with S=the rest of digits of S)

したがって、A=123最終的には次のような結果になります (スペースは「読みやすさ」のためにのみ追加されます):

([2-9][0-9]{2}) | (1(([3-9][0-9]{1}) | (2(([4-9]) | 3))) )
于 2013-08-22T07:48:24.130 に答える
2

私はこれを（PHPで）行いました：

class Converter
{
    const REGEXP_OR     = '|';
    const REGEXP_START  = '^';
    const REGEXP_END    = '$';

    protected $sStart;
    protected $sEnd;
    function __construct($mStart, $mEnd=null)
    {
        if(is_array($mStart) && count($mStart)>1)
        {
            $this->sStart = (string)($mStart[0]);
            $this->sEnd   = (string)($mStart[1]);
        }
        else
        {
            $this->sStart = (string)($mStart);
            $this->sEnd   = (string)($mEnd);
        }
        if((int)($mStart)>(int)($mEnd))
        {
            $this->sStart = $this->sEnd = null;
        }
    }

    public function getRegexp()
    {
        return self::REGEXP_START.$this->_get_regexp_by_range($this->sStart, $this->sEnd).self::REGEXP_END;
    }

    protected function _get_regexp_by_range($sStart, $sEnd, $sOr=self::REGEXP_OR, $sFrom=self::REGEXP_START, $sTill=self::REGEXP_END)
    {
       if(!isset($sStart) || !isset($sEnd))
       {
           return null;
       }
       if((int)($sStart)>(int)($sEnd))
       {
          return null;
       }
       elseif($sStart==$sEnd)
       {
          return $sStart;
       }
       elseif(strlen($sEnd)>strlen($sStart))
       {
          $rgRegexp  = array($this->_get_regexp_by_range($sStart, str_repeat('9', strlen($sStart))));
          for($i=strlen($sStart)+1; $i<strlen($sEnd)-1; $i++)
          {
             $rgRegexp[] = $this->_get_regexp_by_range('1'.str_repeat('0', $i), str_repeat('9', $i+1));
          }
          $rgRegexp[] = $this->_get_regexp_by_range('1'.str_repeat('0', strlen($sEnd)-1), $sEnd);
          return join($sTill.$sOr.$sFrom, $rgRegexp);
       }
       else
       {
          $rgRegexp   = array();
          for($iIntersect=0;$iIntersect<strlen($sStart);$iIntersect++)
          {
             if($sStart[$iIntersect]!=$sEnd[$iIntersect])
             {
                break;
             }
          }
          if($iIntersect)
          {
             return join($sTill.$sOr.$sFrom, array_map(function($sItem) use ($iIntersect, $sStart)
             {
                return substr($sStart, 0, $iIntersect).$sItem;
             }, explode($sTill.$sOr.$sFrom, $this->_get_regexp_by_range(substr($sStart, $iIntersect), substr($sEnd, $iIntersect)))));
          }
          else
          {
             $rgRegexp = array($sStart);
             for($iPos=strlen($sStart)-1; $iPos>0; $iPos--)
             {
                if($sStart[$iPos]+1<10)
                {
                   $rgRegexp[]=substr($sStart, 0, $iPos).'['.($sStart[$iPos]+1).'-'.'9'.']'.str_repeat('[0-9]', strlen($sStart)-$iPos-1);
                }
             }
             if(($sStart[0]+1)<($sEnd[0]-1))
             {
                $rgRegexp[]='['.($sStart[0]+1).'-'.($sEnd[0]-1).']'.str_repeat('[0-9]', strlen($sStart)-1);
             }
             elseif((int)($sStart[0])+1==(int)($sEnd[0])-1)
             {
                $rgRegexp[]=($sStart[0]+1).str_repeat('[0-9]', strlen($sStart)-1);
             }
             for($iPos=1; $iPos<strlen($sEnd); $iPos++)
             {
                if($sEnd[$iPos]-1>=0)
                {
                  $rgRegexp[]=substr($sEnd,0, $iPos).'['.'0'.'-'.($sEnd[$iPos]-1).']'.str_repeat('[0-9]', strlen($sEnd)-$iPos-1);
                }
             }
             $rgRegexp[]=$sEnd;
             return join($sTill.$sOr.$sFrom, $rgRegexp);
          }
       }
    }
}

その後、どの文字列でも正しい結果が得られますが、結果の正規表現は最適なものではないと思います。

$sPattern = (new Converter('1', '1000000000'))->getRegexp();
var_dump(
   preg_match('/'.$sPattern.'/', '10000000000'), 
   preg_match('/'.$sPattern.'/', '100000000'));

とにかく、答えてくれたすべての人に感謝します。

于 2013-08-22T08:52:47.927 に答える