回溯法实现正则匹配判断

*：匹配任意个字符

？：匹配至多1个字符

<?phpclass MNode
{public $strIndex;public $patIndex;public $leftMatch = null;   //精确匹配public $midMatch = null;    //模式匹配public $rightMatch = null;  //不能匹配public function __construct($strIndex, $patIndex){$this->strIndex = $strIndex;$this->patIndex = $patIndex;}
}class RegMatch
{public $root, $match = false;public $string, $pattern;public $strLen, $patLen;public function __construct(string $string, string $pattern){$this->root = new MNode(0, 0);$this->string = $string;$this->pattern = $pattern;$this->strLen = strlen($string);$this->patLen = strlen($pattern);}public function isMatch(){return $this->doMatch($this->root);}protected function doMatch($root){static $matchCount = 0;if (empty($root) || empty($this->string) || empty($this->pattern) || $this->match == true|| $root->strIndex >= $this->strLen || $root->patIndex >= $this->patLen) {if ($root->patIndex >= $this->patLen) {$this->match = true;}return $this->match;}if ($this->string[$root->strIndex] == $this->pattern[$root->patIndex]) {$root->leftMatch = new MNode($root->strIndex + 1, $root->patIndex + 1);$this->doMatch($root->leftMatch);}//模式情况if ($this->pattern[$root->patIndex] == '*') {$root->midMatch = new MNode($root->strIndex + 1, $root->patIndex + 1);$this->doMatch($root->midMatch);if ($this->match == false) {$root->rightMatch = new MNode($root->strIndex, $root->patIndex + 1);$this->doMatch($root->rightMatch);}}if ($this->pattern[$root->patIndex] == '?') {$root->rightMatch = new MNode($root->strIndex, $root->patIndex + 1);$this->doMatch($root->rightMatch);if ($this->match == false && $matchCount <= 1) {$matchCount++;$root->midMatch = new MNode($root->strIndex + 1, $root->patIndex + 1);$this->doMatch($root->midMatch);}}if ($this->match == false && $root->patIndex == 0) {$root->rightMatch = new MNode($root->strIndex + 1, $root->patIndex);$this->doMatch($root->rightMatch);}return $this->match;}
}$obj = new RegMatch('abc', '*c');echo $obj->isMatch();