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

相关文章

来自专栏闻道于事

js登录滑动验证,不滑动无法登陆

js的判断这里是根据滑块的位置进行判断,应该是用一个flag判断 <%@ page language="java" contentType="text/html...

7068
来自专栏hbbliyong

WPF Trigger for IsSelected in a DataTemplate for ListBox items

<DataTemplate DataType="{x:Type vm:HeaderSlugViewModel}"> <vw:HeaderSlug...

4074
来自专栏落花落雨不落叶

canvas画简单电路图

64611
来自专栏飞扬的花生

jsencrypt参数前端加密c#解密

      写程序时一般是通过form表单或者ajax方式将参数提交到服务器进行验证,如何防止提交的请求不被抓包后串改,虽然无法说绝对安全却给非法提交提高了难度...

3919
来自专栏一个会写诗的程序员的博客

Spring Reactor 项目核心库Reactor Core

Non-Blocking Reactive Streams Foundation for the JVM both implementing a Reactiv...

2232
来自专栏pangguoming

Spring Boot集成JasperReports生成PDF文档

由于工作需要,要实现后端根据模板动态填充数据生成PDF文档,通过技术选型,使用Ireport5.6来设计模板,结合JasperReports5.6工具库来调用渲...

1.2K7
来自专栏大内老A

The .NET of Tomorrow

Ed Charbeneau(http://developer.telerik.com/featured/the-net-of-tomorrow/) Exciti...

32410
来自专栏张善友的专栏

Miguel de Icaza 细说 Mix 07大会上的Silverlight和DLR

Mono之父Miguel de Icaza 详细报道微软Mix 07大会上的Silverlight和DLR ,上面还谈到了Mono and Silverligh...

2727
来自专栏张善友的专栏

Mix 10 上的asp.net mvc 2的相关Session

Beyond File | New Company: From Cheesy Sample to Social Platform Scott Hansel...

2627
来自专栏转载gongluck的CSDN博客

cocos2dx 打灰机

#include "GamePlane.h" #include "PlaneSprite.h" #include "BulletNode.h" #include...

5656

扫码关注云+社区