PHP数据结构(三)——运用栈实现括号匹配

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

相关阅读:

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-06-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Phoenix的Android之旅

关于for循环的再次理解

这里的 for循环写法是1.5之后引入的新 feature, 允许开发者用简明的方式遍历一个数组中的元素。

702
来自专栏java学习

ArrayList集合常用的方法详细讲解

在前面我们学习了数组,数组可以保存多个元素,但在某些情况下无法确定到底要保存多少个元素,此时数组将不再适用,因为数组的长度不可变。例如,要保存一个...

904
来自专栏Java帮帮-微信公众号-技术文章全总结

第十八天 集合-泛型&list接口&set接口【面试+工作】

泛型的使用:一般在创建对象时,将未知的类型确定具体的类型。当没有指定泛型时,默认类型为Object类型。

812
来自专栏zaking's

用js来实现那些数据结构11(字典)

  我们这篇文章来说说Map这种数据结构如何用js来实现,其实它和集合(Set)极为类似,只不过Map是【键,值】的形式存储元素,通过键来查询值,Map用于保存...

2757
来自专栏用户2442861的专栏

JAVA中重写equals()方法为什么要重写hashcode()方法说明

重写hashCode()时最重要的原因就是:无论何时,对同一个对象调用hashCode()都应该生成同样的值。如果在将一个对象用put()方法添加进HashM...

431
来自专栏禁心尽力

Java Collection知识总结

首先说说java中常用的集合容器:ArrayList,LinkedList,Vector,HashMap,Hashtable,HashSet,TreeSet。【...

18110
来自专栏郭耀华‘s Blog

Java集合框架(一)—— Collection、Iterator和Foreach的用法

1.Java集合概述   在编程中,常常需要集中存放多个数据。当然我们可以使用数组来保存多个对象。但数组长度不可变化,一旦在初始化时指定了数组长度,则这个数组长...

3129
来自专栏Java帮帮-微信公众号-技术文章全总结

16(02)总结泛型

2:泛型(掌握) (1)泛型概述 是一种把明确类型的工作推迟到创建对象或者调用方法的时候才去明确的特殊的类型。 (2)格式: <数据类型> 注意:该数...

3227
来自专栏向治洪

JAVA中重写equals()方法的同时要重写hashcode()方法

object对象中的 public boolean equals(Object obj),对于任何非空引用值 x 和 y,当且仅当 x 和 y 引用同一个对象时...

1946
来自专栏鸿的学习笔记

Python和Scala的操作符

在聊完类和对象之后,我们要理解一件事,无论是在Scala还是Python,每一个值都是对象,在某种程度上来说,这两门语言都是更加纯粹的面向对象的语言。两者也都支...

452

扫码关注云+社区