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 条评论
登录 后参与评论

相关文章

来自专栏JackeyGao的博客

Golang flag 获取多个值

但是在某些情况下,我们要对一个key指定多个值。 并获取多个值得数组。 这时我们需要定义一个Type Value接口类型

1282
来自专栏Ryan Miao

java基础面试题

参考:http://blog.csdn.net/jackfrued/article/details/44921941 说未经允许不转载,我只好参考了。 1.面向...

3635
来自专栏开发与安全

《linux c 编程一站式学习》课后部分习题解答

1、假设变量x和n是两个正整数,我们知道x/n这个表达式的结果要取Floor,例如x是17,n是4,则结果是4。如果希望结果取Ceiling应该怎么写表达式呢?...

3496
来自专栏绿巨人专栏

TypeScript中的怪语法

1093
来自专栏calvin

【nodejs】让nodejs像后端mvc框架(asp.net mvc)一样处理请求--参数自动映射篇(6/8)

路由、action的扫描、发现、注册搞定之后,后来我发现在我们的action里面获取参数往往都是通过request对象来一个一个获取。同样的一行代码我们不厌其烦...

1022
来自专栏Ryan Miao

velocity的一些用法

velocity模板其实就是java不分语法的翻译,用到的属性还是java的方法,get,set,等 1.截取部分字段substring 1 原始字符串:$!a...

34911
来自专栏架构说

Leetcode 200 Number of Islands 岛的个数

1. 遍历每一个结点,如果某结点是陆地且未访问过,岛数目加1,修改未访问标志位,然后把该点放入队列中,以备扩展岛屿使用,进入2 2. 队列不为空时,取出点,然...

1463
来自专栏Java面试通关手册

Java多线程学习(二)synchronized关键字(1)

Java面试通关手册(Java学习指南,欢迎Star,会一直完善下去,欢迎建议和指导):https://github.com/Snailclimb/Java_G...

2184
来自专栏小灰灰

Java容器篇小结之Map自问自答

采用问答的方式对常见的问题进行整理小结 I. Map篇 0. 什么是Map 看到这个有点懵逼,一时还真不知道怎么解释,能让完全没有接触过的人都能听懂 想到生活...

19210
来自专栏me的随笔

Python知识梳理

我们可以使用type()函数类获取对象的类型,Python3中内置数据类型包括:None,int,float,complex,str,list,dict,tup...

1232

扫码关注云+社区