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

相关文章

来自专栏土豆专栏

Java面试之数组

Array:它是数组,申明数组的时候就要初始化并确定长度,长度不可变,而且它只能存储同一类型的数据,比如申明为String类型的数组,那么它只能存储S听类型数据...

1114
来自专栏python学习指南

python切片

本篇将介绍Python的切片操作,切片支持的数据类型有列表、字符串、元祖,更多内容请参考:Python学习指南 切片是什么? 切片操作符是序列名后跟一个方...

1877
来自专栏个人随笔

房上的猫:if选择结构

一.基本if结构: ? ?  1.定义:if选择结构是根据条件判断之后再做处理的一种语法结构!  2.逻辑:首先对条件进行判断   >如果为真,则执行代码块 ...

34512
来自专栏行者常至

003.python科学计算库pandas(上)

版权声明:本文为博主原创文章,允许转载,请标明出处。 https://blog.csdn.net/qwdafedv/article/deta...

472
来自专栏机器学习从入门到成神

队列和栈面试题(一)— 请编写一个程序,按升序对栈进行排序,要求最多只能使用一个额外的栈存放临时数据

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

792
来自专栏我是攻城师

Python之numpy的ndarray数组使用方法介绍

NumPy的全名为Numeric Python,是一个开源的Python科学计算库,它包括:

903
来自专栏IT派

Python爬虫库-Beautiful Soup的使用

Beautiful Soup是一个可以从HTML或XML文件中提取数据的Python库,简单来说,它能将HTML的标签文件解析成树形结构,然后方便地获取到指定标...

1153
来自专栏程序员互动联盟

【面试宝典】写一个函数将两个数交换

没有参加过面试的同学可能会很忐忑,面试都会出些什么题呢?其实一般情况下,大部分的面试题都是比较基础的。关于如何交换两个数字,应该是非常简单的问题了。看下面几个函...

3328
来自专栏工科狗和生物喵

【计算机本科补全计划】Java学习笔记(七) 常用的类

正文之前 没辙,为了我的一个完整的教程,不得不忍痛继续写一些简单的东西,虽然这些网上都有,但是要纳进我的体系还是需要写进来的,以后自己要看了, 直接就可以看到了...

3236
来自专栏web前端教室

5分钟学会javascript闭包(一)

先来定义,能读取其它函数内部变量的函数,它可以将函数内部和外部连接起来。 javascript有二种变量的作用域, 一是全局变量,二是局部变量 根据javasc...

1617

扫描关注云+社区