PHP数据结构(三)——运用栈实现括号匹配
(原创内容,转载请注明来源,谢谢)
栈在数据结构上是一种特殊的线性表,其限制是仅允许在表的一端进行插入和删除运算,即LIFO(后进先出),越往入栈的数据在取出是越早被取出。允许操作的一端称为栈顶,另一端称为栈底。
对于栈,可以理解为一个大箱子里面的物品,越晚放进去的东西越早被拿出来。栈的数据模型大致如下:
下文用PHP实现栈类,并实现括号匹配方法。
注:括号匹配,即输入一串内容,判断括号是否正确匹配。括号类型有()、[]、{}三种,要求左括号的右边出现的第一个括号只能是左括号或者与左括号对应的右括号。
下面代码尝试三种输入,其中一种正确两种错误的。代码允许结果如下。
源代码如下。
<?php
class stack{
private$top;//定义栈顶
private$bottom;//定义栈底
private$stackdata;//定义栈数据,定义为private,只允许push和pop操作
private$size;//定义栈容量,第一个位置为bottom位,不能放数据
//构造函数,生成基础的栈
publicfunction __construct($stacksize=10){
$this->top= 0;
$this->bottom= 0;
$this->stackdata= array();
$this->size= $stacksize;
}
//初始化栈,规定输入为一维数组
publicfunction init($arr){
if(($this->size-1)<count($arr)){
echo'超出栈设定容量';
returnfalse;
}else{
foreach($arras $item){
$this->top++;
$this->stackdata[$this->top]= $item;
}
returntrue;
}
}
//重新设定栈容量
publicfunction resize($renum){
if(($renum-1)<count($this->stackdata)){
echo'容量小于现有数据';
returnfalse;
}else{
$this->size= $renum;
returntrue;
}
}
//入栈
publicfunction push($arr){
//首先比较输入的数组是否查出范围
$arr_len= 0;
if(!is_array($arr)){
$arr_len= 1;
}else{
$arr_len= count($arr);
}
$enough= $this->size-count($this->stackdata)-$arr_len-1;
if($enough<0){
echo'超出栈设定容量';
returnfalse;
}elseif(!is_array($arr)){
$this->top++;
$this->stackdata[$this->top]= $arr;
returntrue;
}else{
foreach($arras $item){
$this->top++;
$this->stackdata[$this->top]= $item;
}
returntrue;
}
}
//出栈
publicfunction pop(){
if($this->top==$this->bottom){
echo'栈为空';
returnfalse;
}else{
$data= $this->stackdata[$this->top];
unset($this->stackdata[$this->top]);
$this->top--;
return$data;
}
}
//获取栈顶内容
publicfunction getTop(){
if($this->top==$this->bottom){
echo'栈为空';
returnfalse;
}else{
return$this->stackdata[$this->top];
}
}
}
//实现括号匹配判定
//括号类型()、{}、[],不允许出现{]等
function expressionMatch($expr){
$arr_left =array('(', '[', '{');
$arr_right= array(')', ']', '}');
$arr_match= array(
'('=> ')',
'['=> ']',
'{'=> '}'
);//匹配
$arr_num =array(
'('=> 0,
'['=> 0,
'{'=>0
);//使用次数
$mystack =new stack();
$mystack->resize(strlen($expr)+1);
$i = 0;
$tips = '结论:';
$result =false;
while($i<strlen($expr)){
$word= $expr[$i++];
if(in_array($word,$arr_right)){
$match= $mystack->pop();
if($arr_match[$match]!=$word){
$tips .= " Missing $arr_match[$match] before$word";
$result= false;
break;
}else{
$arr_num[$match]++;
}
}
if(in_array($word,$arr_left)){
$mystack->push($word);
}
$result= true;
}
if($result){
foreach($arr_numas $key=>$val){
$tips.= ' '.$key.$arr_match[$key].'共出现'.$val.'对 ';
}
}
echo '输入:'.$expr.' ===>>> '.$tips.'<br />';
return$tips;
}
$expr_true = '{test[testc](a)[testb{test}]d}';
expressionMatch($expr_true);
$expr_false1 = '{test[ad)d}';
expressionMatch($expr_false1);
$expr_false2 = '{test[ad]a)d}';
expressionMatch($expr_false2);
?>
针对栈,近期将使用并实现各类算法,诸如数学表达式、行输入程序等。敬请期待。
——written by linhxx 2017.06.16
相关阅读: