The definition of the php stack, the push and pop methods, and the complete implementation example of the calculator

The stack is a type of linear table. Its characteristic is last in first out. It can be understood that the stack is like a box for storing things. The first things are put in at the bottom, and the last things are put in. It's on the upper level, because the things on the upper level hold down the things on the bottom level. If the things on the lower level want to get out, they have to remove the things on the upper level first.

Introduction code:

data class: It is the class that stores data. () is what is to be put into the stack
stack class: It is the class of the stack, and the entire stack is in this class

Main method:

Enter Stack push_stack($data) detects whether the stack is full, and if not, pushes data onto the stack.
Pop_stack($data) detects whether the stack is empty. If it is not empty, it can be popped.
Read the top element of the stack top_stack(). If the stack is not empty, return the data at the top of the current stack.

The following is the code:

<?php
/**
* Author Been
**/
class data{
  //数据
  private $data;
  public function construct($data){
    $this->data=$data;
    echo $data.":哥入栈了！<br>";
  }
  public function getData(){
    return $this->data;
  }
  public function destruct(){
    echo $this->data."：哥走了！<br>";
  }
}
class stack{
  private $size;
  private $top;
  private $stack=array();
  public function construct($size){
    $this->Init_Stack($size);
  }
  //初始化栈
  public function Init_Stack($size){
    $this->size=$size;
    $this->top=-1;
  }
  //判断栈是否为空
  public function Empty_Stack(){
    if($this->top==-1)return 1;
    else return 0;
  }
  //判断栈是否已满
  public function Full_Stack(){
    if($this->top<$this->size-1)return 0;
    else return 1;
  }
  //入栈
  public function Push_Stack($data){
    if($this->Full_Stack())echo "栈满了<br />";
    else $this->stack[++$this->top]=new data($data);
  }
  //出栈
  public function Pop_Stack(){
    if($this->Empty_Stack())echo "栈空着呢<br />";
    else unset($this->stack[$this->top--]);
  }
  //读取栈顶元素
  public function Top_Stack(){
    return $this->Empty_Stack()?"栈空无数据！":$this->stack[$this->top]->getData();
  }
}
$stack=new stack(4);
$stack->Pop_Stack();
$stack->Push_Stack("aa");
$stack->Push_Stack("aa1");
$stack->Pop_Stack("aa1");
$stack->Push_Stack("aa2");
$stack->Push_Stack("aa3");
$stack->Push_Stack("aa4");
echo $stack->Top_Stack(),&#39;<br />&#39;;
$stack->Push_Stack("aa5");
$stack->Push_Stack("aa6");
$stack->Pop_Stack();
$stack->Pop_Stack();
$stack->Pop_Stack();
$stack->Pop_Stack();
$stack->Pop_Stack();
$stack->Pop_Stack();

Running result:

栈空着呢
aa:哥入栈了！
aa1:哥入栈了！
aa1：哥走了！
aa2:哥入栈了！
aa3:哥入栈了！
aa4:哥入栈了！
aa4
栈满了
栈满了
aa4：哥走了！
aa3：哥走了！
aa2：哥走了！
aa：哥走了！
栈空着呢
栈空着呢

Case: Stack-based advanced calculator

When we get a string operation expression, how do we get its operation result?

At this time we can use the stack algorithm to solve this problem very cleverly.

The idea is this: (We use the PHP function substr loop to intercept this string operation expression, and take out the value of this string in turn [we have to intercept from the first character], we will start to intercept the position Set it as a cyclically growing variable, initialized to [$index=0]). At the same time, we need to create two stacks, one to store numbers [$numStack], and one to store operators [$operStack]. We also need one that can judge Whether it is a function of arithmetic symbols, put the intercepted value each time into this custom function, return an identifier that can be distinguished as a number or operator, and determine whether the value is a number or an operator by judging this identifier If the operator is a number, insert it into the number stack. If it is an operator, insert it into the symbol stack. If you insert the number stack, you can insert it directly, but the symbol stack needs special processing [[If the symbol stack is empty, insert it directly, not empty: we need to compare the operation priority of the inserted symbol with the symbols in the stack (canDefine a function to determine the symbol priority. Assume * and / are 1 and + and - are assumed to be 0. Assume that larger numbers have higher priority, so you can get Operator priority), when the priority of the symbol to be inserted is less than or equal to the operator priority at the top of the stack, two values ​​​​are popped from the number stack. An operator is popped from the symbol stack to operate on them]

The following is a php Example [Refer to Teacher Han Shunping's PHP algorithm tutorial]

<html>
<head>
<meta http-equiv=&#39;content-type&#39; content=&#39;text/html;charset=utf-8&#39;/>
</head>
<h1>高级计算器</h1>
<?php
/**
 * 一个栈类
 */
class MyStack{
      public $top=-1;//默认是-1，表示该栈是空的
      public $maxSize=15;//$maxSize表示栈最大容量
      public $stack=array();//
      //入栈的操作
      public function push($val)
      {
        //先判断栈是否已经满了
        if($this->top==$this->maxSize-1){
          echo &#39;<br/>栈满，不能添加&#39;;
          return;
        }
        $this->top++;
        $this->stack[$this->top]=$val;
      }
      //出栈的操作,就是把栈顶的值取出
      public function pop()
      {
        //判断是否栈空
        if($this->top==-1){
          echo &#39;<br/>栈空1&#39;;
          return;
        }
        //把栈顶的值，取出
        $topVal=$this->stack[$this->top];
        $this->top--;
        return $topVal;
      }
      //显示栈的所有数据的方法.
      public function showStack()
      {
        if($this->top==-1){
          echo &#39;<br/>栈空2&#39;;
          return;
        }
        echo &#39;<br/>当前栈的情况是....&#39;;
        for($i=$this->top;$i>-1;$i--){
          echo &#39;<br/> stack[&#39;.$i.&#39;]=&#39;.$this->stack[$i];
        }
      }
      //判断是否是一个运算符
      public function isOper($val)
      {
        if ($val==&#39;+&#39;||$val==&#39;-&#39;||$val==&#39;*&#39;||$val==&#39;/&#39;)
        {
          return true;
        }
      }
      //判断栈是否为空
      public function isEmpty()
      {
        if ($this->top==-1) return true;
      }
      /**
       * 比较运算符的优先级
       * 我把 * 和/运算符的优先级看作1
       * +和- 看作0
       * 通过它们之间的比较就能得出它们的优先级谁更高
       */
      public function PRI($oper)
      {
        if ($oper==&#39;*&#39;||$oper==&#39;/&#39;)
        {
          return 1;
        } else if ($oper==&#39;+&#39;||$oper==&#39;-&#39;) {
          return 0;
        }
      }
      //返回栈顶端的值
      public function getTop()
      {
        return $this->stack[$this->top];
      }
      //计算
      public function getResult($num1,$num2,$oper)
      {
        switch ($oper)
        {
          case &#39;+&#39;:
            $res = $num2+$num1;
          break;
          case &#39;-&#39;:
            $res = $num2-$num1;
          break;
          case &#39;*&#39;:
            $res = $num2*$num1;
          break;
          case &#39;/&#39;:
            $res = $num2/$num1;
          break;
        }
        return $res;
      }
}
//需要进行运算的表达式
$str = &#39;12+5*2+3-5*2&#39;;
//字符串的指针
$index = 0;
//声明一个用于组合联系数字的变量
$keepNum = &#39;&#39;;
//定义一个数栈和一个符号栈
$numsStack=new MyStack();
$operStack=new MyStack();
while (true)
{
  $val = mb_substr($str,$index,1);
  //如果是一个符号就入符号栈 否则入数栈
  if ($operStack->isOper($val)==true)
  {
    //符号入栈前需要判断一下 栈为空直接入栈 不为空需要比较当前运算符与栈顶端的运算符
    //如果当前运算符的优先级低于栈内的 则需要运算
    if ($operStack->isEmpty())
    {
      $operStack->push($val);
    } else {
       while (!$operStack->isEmpty()&&$operStack->PRI($val)<=$operStack->PRI($operStack->getTop()))
       {
         //当前符号的优先级要直到高于栈内的时候才能入栈 否则要计算
        //当前运算符的优先级低于栈内的 则运算
        $num1 = $numsStack->pop();
        $num2 = $numsStack->pop();
        $oper = $operStack->pop();
        $res = $numsStack->getResult($num1,$num2,$oper);
        //计算完毕将结果入栈
        $numsStack->push($res);
       }
      //把当前这个符号再入符号栈
      $operStack->push($val);
        }
  } else {
    //考虑如果是连续数字的问题
    $keepNum.=$val;
    //先判断是否已经到字符串最后.如果已经到最后，就直接入栈.
    if ($index==mb_strlen($str)-1)
    {
      $numsStack->push($keepNum);//是数字直接入栈
    } else {
      //要判断一下$ch字符的下一个字符是数字还是符号.
      if ($operStack->isOper(mb_substr($str,$index+1,1)))
      {
        $numsStack->push($keepNum);
        $keepNum=&#39;&#39;;
      }
    }
  }
  $index++;//让$index指向下一个字符.
  if ($index==mb_strlen($str)) break;//已扫描到字符串的末尾 就退出while循环
}
/*
4. 当扫描完毕后，就依次弹出数栈和符号栈的数据，并计算，最终留在数栈的值，就是运算结果,只有符号栈不空就一直计算
*/
while (!$operStack->isEmpty())
{
  $num1 = $numsStack->pop();
  $num2 = $numsStack->pop();
  $oper = $operStack->pop();
  $res = $numsStack->getResult($num1,$num2,$oper);
  //计算完毕将结果入栈
  $numsStack->push($res);
}
//当退出while后，在数栈一定有一个数，这个数就是最后结果
echo $str.&#39;=&#39;.$numsStack->getTop();
?>

Running results:

12+5*2+3-5*2=15

The above is the detailed content of The definition of the php stack, the push and pop methods, and the complete implementation example of the calculator. For more information, please follow other related articles on the PHP Chinese website!