PHPベースのスタックデータ構造と括弧マッチングアルゴリズムの例
2257 ワード
本明細書の例では、PHPベースのスタックデータ構造および括弧マッチングアルゴリズムの実装について説明する.皆さんの参考にしてください.具体的には以下の通りです.
スタックは、後進先出、すなわちLIFOを体現している.キューは、先進先出、すなわちFIFOを体現している.
スタック操作:
または
例:{2*3[x*y+5+m*(i-j)/3]+k*(4+(t+9)}などの数学式が正しいかどうかを検証します.
分析:1つの式の正しいかどうかは、各种の括弧のマッチングに现れ、括弧が完全にマッチングし、式は问题ありません.では、どのように1つの式の中の括弧のマッチングを検査しますか.多くの人が正則を使いたいと思っています.この正則がどのように書かれ、どのようにネスト関係を実現するか分からない.この時は桟が役に立った.下のコードを見てください.
上記のコードのスタックはarray_popとarray_push実現;同じようにarrayも使えますshiftとarray_unshift実装.
附:キューアクション
または
PHPについてもっと兴味のある読者は、「PHPデータ构造とアルゴリズムチュートリアル」、「phpプログラム设计アルゴリズム総括」、「PHP配列(Array)操作テクニック大全」、「php文字列(string)用法総括」、「PHP常用遍歴アルゴリズムとテクニック総括」、「PHP数学演算テクニック総括」
ここで述べたことが皆さんのPHPプログラム設計に役立つことを願っています.
スタックは、後進先出、すなわちLIFOを体現している.キューは、先進先出、すなわちFIFOを体現している.
スタック操作:
array_pop() //
array_push() //
または
array_shift()//
array_unshift()//
例:{2*3[x*y+5+m*(i-j)/3]+k*(4+(t+9)}などの数学式が正しいかどうかを検証します.
分析:1つの式の正しいかどうかは、各种の括弧のマッチングに现れ、括弧が完全にマッチングし、式は问题ありません.では、どのように1つの式の中の括弧のマッチングを検査しますか.多くの人が正則を使いたいと思っています.この正則がどのように書かれ、どのようにネスト関係を実現するか分からない.この時は桟が役に立った.下のコードを見てください.
function checkMatch($str){
if(!$str)return false;
$arr = str_split($str);
$left = array('{','[','(');
$right = array('}',']',')');
$stack = array();
reset($arr); // while reset(),
while(list($key, $val) = each($arr)){
if(in_array($val,$left,true)){
//
array_push($stack,$val); //
}else if(in_array($val,$right,true)){
$topStack = end($stack); // , ( ), 。
if(isset($topStack) && !empty($topStack)){
if(array_search($val,$right,true) === array_search($topStack,$left,true)){ //
//
array_pop($stack); // pop
}else{
//
return false; //
}
}else{
//
return false; // ,
}
}
}
return empty($stack) ? true : false; // $stack ,
}
$test = '{2*3[x*y+5+m*(i-j)/3]+k*(4+(t+9))}';
var_dump ( checkMatch ( $test ) );
上記のコードのスタックはarray_popとarray_push実現;同じようにarrayも使えますshiftとarray_unshift実装.
附:キューアクション
array_shift() //
array_push() //
または
array_unshift //
array_pop //
PHPについてもっと兴味のある読者は、「PHPデータ构造とアルゴリズムチュートリアル」、「phpプログラム设计アルゴリズム総括」、「PHP配列(Array)操作テクニック大全」、「php文字列(string)用法総括」、「PHP常用遍歴アルゴリズムとテクニック総括」、「PHP数学演算テクニック総括」
ここで述べたことが皆さんのPHPプログラム設計に役立つことを願っています.