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