当前位置：首页 > PHP教程 > php应用 > 列表

PHP栈的定义、入栈出栈方法及基于堆栈实现的计算器完整实例

发布:smiling　来源: PHP粉丝网 　添加日期：2021-08-17 21:48:30　浏览: 评论：0　

这篇文章主要介绍了PHP栈的定义、入栈出栈方法及基于堆栈实现的计算器,结合实例形式较为详细的分析了php定义与使用栈的基本方法,并结合完整实例形式给出了php基于堆栈实现高级计算器功能的相关操作技巧,需要的朋友可以参考下。

本文实例讲述了PHP栈的定义、入栈出栈方法及基于堆栈实现的计算器，分享给大家供大家参考，具体如下：

栈是线性表的一种，他的特点是后入先出，可以这么理解，栈就像一个存东西的盒子，先放进去的在最底层，后放进去的在上层，因为上层的东西把底层的东西压住了，下层的想要出去就必须把上层的先拿开才行。

介绍代码：

data类：就是存放数据的类。（）就是要放入栈的东西

stack类：是栈的类，整个对栈就在这个类中

主要方法：

入栈push_stack（$data）检测栈是否已满，如果没满就让数据入栈。

出栈pop_stack($data)检测栈是否为空，如果不空可以出栈

读取栈顶元素top_stack()如果栈不空，返回当前栈顶部的数据。

下边是代码：

  1. <?php 
  2. /** 
  3. * Author Been 
  4. **/ 
  5. class data{ 
  6.   //数据 
  7.   private $data; 
  8.   public function __construct($data){ 
  9.     $this->data=$data; 
  10.     echo $data.":哥入栈了！<br>"; 
  11.   } 
  12.   public function getData(){ 
  13.     return $this->data; 
  14.   } 
  15.   public function __destruct(){ 
  16.     echo $this->data."：哥走了！<br>"; 
  17.   } 
  18. } 
  19. class stack{ 
  20.   private $size; 
  21.   private $top; 
  22.   private $stack=array(); 
  23.   public function __construct($size){ 
  24.     $this->Init_Stack($size); 
  25.   } 
  26.   //初始化栈 
  27.   public function Init_Stack($size){ 
  28.     $this->size=$size; 
  29.     $this->top=-1; 
  30.   } 
  31.   //判断栈是否为空 
  32.   public function Empty_Stack(){ 
  33.     if($this->top==-1)return 1; 
  34.     else return 0; 
  35.   } 
  36.   //判断栈是否已满 
  37.   public function Full_Stack(){ 
  38.     if($this->top<$this->size-1)return 0; 
  39.     else return 1; 
  40.   } 
  41.   //入栈 
  42.   public function Push_Stack($data){ 
  43.     if($this->Full_Stack())echo "栈满了<br />"; 
  44.     else $this->stack[++$this->top]=new data($data); 
  45.   } 
  46.   //出栈 
  47.   public function Pop_Stack(){ 
  48.     if($this->Empty_Stack())echo "栈空着呢<br />"; 
  49.     else unset($this->stack[$this->top--]); 
  50.   } 
  51.   //读取栈顶元素 
  52.   public function Top_Stack(){ 
  53.     return $this->Empty_Stack()?"栈空无数据！":$this->stack[$this->top]->getData(); 
  54.   } 
  55. } 
  56. $stack=new stack(4); 
  57. $stack->Pop_Stack(); 
  58. $stack->Push_Stack("aa"); 
  59. $stack->Push_Stack("aa1"); 
  60. $stack->Pop_Stack("aa1"); 
  61. $stack->Push_Stack("aa2"); 
  62. $stack->Push_Stack("aa3"); 
  63. $stack->Push_Stack("aa4"); 
  64. echo $stack->Top_Stack(),'<br />'; 
  65. $stack->Push_Stack("aa5"); 
  66. $stack->Push_Stack("aa6"); 
  67. $stack->Pop_Stack(); 
  68. $stack->Pop_Stack(); 
  69. $stack->Pop_Stack(); 
  70. $stack->Pop_Stack(); 
  71. $stack->Pop_Stack(); 
  72. $stack->Pop_Stack(); 

运行结果：

  1. 栈空着呢 
  2. aa:哥入栈了！ 
  3. aa1:哥入栈了！ 
  4. aa1：哥走了！ 
  5. aa2:哥入栈了！ 
  6. aa3:哥入栈了！ 
  7. aa4:哥入栈了！ 
  8. aa4 
  9. 栈满了 
  10. 栈满了 
  11. aa4：哥走了！ 
  12. aa3：哥走了！ 
  13. aa2：哥走了！ 
  14. aa：哥走了！ 
  15. 栈空着呢 
  16. 栈空着呢 

案例：基于堆栈的高级计算器

当我们得到一个字符串运算式该如何去得出它的运算结果呢？

这时候我们就能使用堆栈的算法很巧妙的解决这个问题。

思路是这样的：（我们利用php函数substr循环去截取这个字符串运算式，依次取出这个字符串的值【我们得从第一个字符开始截取】，我们将开始截取位置设为一个循环增长的变量，初始化为【$index=0】）,同时还需要创建两个栈，一个专门存放数字【$numStack】，一个存放运算符【$operStack】，我们还需要一个可以判断是否是运算符号的函数，将每次截取的值放入这个自定义函数中，返回一个可以区别为数字或运算符的标识，通过对这个标识的判断确定值是数字还是运算符，是数字就插入数栈，是运算符的话就插入符号栈。插入数栈的话可直接插入，但是符号栈的话需要特殊处理一下[【如果符号栈为空则直接插入，不为空：我们要将插入的符号与栈内的符号进行运算优先级比较（可以定义一个函数来判定符号优先级，把 *  和 / 假定为1  把 + 和 - 假定为0  假设数字大的优先级高，如此就能得出运算符优先级），当待插入的符号优先级小于等于栈内顶端的运算符优先级，就从数栈弹出两个值  符号栈弹出一个运算符 将它们进行运算】

下面是一个php的实例【参考自韩顺平老师的php算法教程】

  1. <html> 
  2. <head> 
  3. <meta http-equiv='content-type' content='text/html;charset=utf-8'/> 
  4. </head> 
  5. <h1>高级计算器</h1> 
  6. <?php 
  7. /** 
  8.  * 一个栈类 
  9.  */ 
  10. class MyStack{ 
  11.       public $top=-1;//默认是-1，表示该栈是空的 
  12.       public $maxSize=15;//$maxSize表示栈最大容量 
  13.       public $stack=array();// 
  14.       //入栈的操作 
  15.       public function push($val) 
  16.       { 
  17.         //先判断栈是否已经满了 
  18.         if($this->top==$this->maxSize-1){ 
  19.           echo '<br/>栈满，不能添加'; 
  20.           return; 
  21.         } 
  22.         $this->top++; 
  23.         $this->stack[$this->top]=$val; 
  24.       } 
  25.       //出栈的操作,就是把栈顶的值取出 
  26.       public function pop() 
  27.       { 
  28.         //判断是否栈空 
  29.         if($this->top==-1){ 
  30.           echo '<br/>栈空1'; 
  31.           return; 
  32.         } 
  33.         //把栈顶的值，取出 
  34.         $topVal=$this->stack[$this->top]; 
  35.         $this->top--; 
  36.         return $topVal; 
  37.       } 
  38.       //显示栈的所有数据的方法. 
  39.       public function showStack() 
  40.       { 
  41.         if($this->top==-1){ 
  42.           echo '<br/>栈空2'; 
  43.           return; 
  44.         } 
  45.         echo '<br/>当前栈的情况是....'; 
  46.         for($i=$this->top;$i>-1;$i--){ 
  47.           echo '<br/> stack['.$i.']='.$this->stack[$i]; 
  48.         } 
  49.       } 
  50.       //判断是否是一个运算符 
  51.       public function isOper($val) 
  52.       { 
  53.         if ($val=='+'||$val=='-'||$val=='*'||$val=='/') 
  54.         { 
  55.           return true; 
  56.         } 
  57.       } 
  58.       //判断栈是否为空 
  59.       public function isEmpty() 
  60.       { 
  61.         if ($this->top==-1) return true; 
  62.       } 
  63.       /** 
  64.        * 比较运算符的优先级 
  65.        * 我把 * 和/运算符的优先级看作1 
  66.        * +和- 看作0 
  67.        * 通过它们之间的比较就能得出它们的优先级谁更高 
  68.        */ 
  69.       public function PRI($oper) 
  70.       { 
  71.         if ($oper=='*'||$oper=='/') 
  72.         { 
  73.           return 1; 
  74.         } else if ($oper=='+'||$oper=='-') { 
  75.           return 0; 
  76.         } 
  77.       } 
  78.       //返回栈顶端的值 
  79.       public function getTop() 
  80.       { 
  81.         return $this->stack[$this->top]; 
  82.       } 
  83.       //计算 
  84.       public function getResult($num1,$num2,$oper) 
  85.       { 
  86.         switch ($oper) 
  87.         { 
  88.           case '+': 
  89.             $res = $num2+$num1; 
  90.           break; 
  91.           case '-': 
  92.             $res = $num2-$num1; 
  93.           break; 
  94.           case '*': 
  95.             $res = $num2*$num1; 
  96.           break; 
  97.           case '/': 
  98.             $res = $num2/$num1; 
  99.           break; 
  100.         } 
  101.         return $res; 
  102.       } 
  103. } 
  104. //需要进行运算的表达式 
  105. $str = '12+5*2+3-5*2'; 
  106. //字符串的指针 
  107. $index = 0; 
  108. //声明一个用于组合联系数字的变量 
  109. $keepNum = ''; 
  110. //定义一个数栈和一个符号栈 
  111. $numsStack=new MyStack(); 
  112. $operStack=new MyStack(); 
  113. while (true) 
  114. { 
  115.   $val = mb_substr($str,$index,1); 
  116.   //如果是一个符号就入符号栈 否则入数栈 
  117.   if ($operStack->isOper($val)==true) 
  118.   { 
  119.     //符号入栈前需要判断一下 栈为空直接入栈 不为空需要比较当前运算符与栈顶端的运算符 
  120.     //如果当前运算符的优先级低于栈内的 则需要运算 
  121.     if ($operStack->isEmpty()) 
  122.     { 
  123.       $operStack->push($val); 
  124.     } else { 
  125.        while (!$operStack->isEmpty()&&$operStack->PRI($val)<=$operStack->PRI($operStack->getTop())) 
  126.        { 
  127.          //当前符号的优先级要直到高于栈内的时候才能入栈 否则要计算 
  128.         //当前运算符的优先级低于栈内的 则运算 
  129.         $num1 = $numsStack->pop(); 
  130.         $num2 = $numsStack->pop(); 
  131.         $oper = $operStack->pop(); 
  132.         $res = $numsStack->getResult($num1,$num2,$oper); 
  133.         //计算完毕将结果入栈 
  134.         $numsStack->push($res); 
  135.        } 
  136.       //把当前这个符号再入符号栈 
  137.       $operStack->push($val); 
  138.         } 
  139.   } else { 
  140.     //考虑如果是连续数字的问题 
  141.     $keepNum.=$val; 
  142.     //先判断是否已经到字符串最后.如果已经到最后，就直接入栈. 
  143.     if ($index==mb_strlen($str)-1) 
  144.     { 
  145.       $numsStack->push($keepNum);//是数字直接入栈 
  146.     } else { 
  147.       //要判断一下$ch字符的下一个字符是数字还是符号. 
  148.       if ($operStack->isOper(mb_substr($str,$index+1,1))) 
  149.       { 
  150.         $numsStack->push($keepNum); 
  151.         $keepNum=''; 
  152.       } 
  153.     } 
  154.   } 
  155.   $index++;//让$index指向下一个字符. 
  156.   if ($index==mb_strlen($str)) break;//已扫描到字符串的末尾 就退出while循环 
  157. } 
  158. /* 
  159. 4. 当扫描完毕后，就依次弹出数栈和符号栈的数据，并计算，最终留在数栈的值，就是运算结果,只有符号栈不空就一直计算 
  160. */ 
  161. while (!$operStack->isEmpty()) 
  162. { 
  163.   $num1 = $numsStack->pop(); 
  164.   $num2 = $numsStack->pop(); 
  165.   $oper = $operStack->pop(); 
  166.   $res = $numsStack->getResult($num1,$num2,$oper); 
  167.   //计算完毕将结果入栈 
  168.   $numsStack->push($res); 
  169. } 
  170. //当退出while后，在数栈一定有一个数，这个数就是最后结果 
  171. echo $str.'='.$numsStack->getTop(); 
  172. ?> 

运行结果：12+5*2+3-5*2=15

Tags: PHP栈 PHP堆栈

分享到：

相关文章

推荐文章

热门文章

最新评论文章