Of Stack

The definition of PHP stack the method of stack in and stack out and a complete example of calculator based on stack implementation

  • 2021-08-10 07:31:37
  • OfStack

In this paper, the definition of PHP stack, the method of stack-in and stack-out and the calculator based on stack are described with examples. Share it for your reference, as follows:

Stack is a kind of linear table, which is characterized by last-in, first-out. It can be understood that stack is like a box for storing things, which is put in at the bottom first, and then put in at the upper layer, because the upper layer presses the bottom layer, and the lower layer must take the upper layer away if it wants to go out.

Description code:

data class: Is the class that holds the data. () is something to put on the stack
stack class: Is the stack class, the entire pair stack is in this class

Main methods:

Stack push_stack ($data) detects whether the stack is full, and if it is not, puts the data on the stack.
pop_stack ($data) detects whether the stack is empty. If it is not empty, you can leave the stack
Read the top stack element top_stack () If the stack is not empty, return the data at the top of the current stack.

Here's the code: 


<?php
/**
* Author Been
**/
class data{
  // Data 
  private $data;
  public function __construct($data){
    $this->data=$data;
    echo $data.": Brother is in the stack! <br>";
  }
  public function getData(){
    return $this->data;
  }
  public function __destruct(){
    echo $this->data." I'm gone! <br>";
  }
}
class stack{
  private $size;
  private $top;
  private $stack=array();
  public function __construct($size){
    $this->Init_Stack($size);
  }
  // Initialization stack 
  public function Init_Stack($size){
    $this->size=$size;
    $this->top=-1;
  }
  // Determine whether the stack is empty 
  public function Empty_Stack(){
    if($this->top==-1)return 1;
    else return 0;
  }
  // Determine if the stack is full 
  public function Full_Stack(){
    if($this->top<$this->size-1)return 0;
    else return 1;
  }
  // Stack 
  public function Push_Stack($data){
    if($this->Full_Stack())echo " The stack is full <br />";
    else $this->stack[++$this->top]=new data($data);
  }
  // Out of stack 
  public function Pop_Stack(){
    if($this->Empty_Stack())echo " The stack is empty <br />";
    else unset($this->stack[$this->top--]);
  }
  // Read the top element of the stack 
  public function Top_Stack(){
    return $this->Empty_Stack()?" The stack is empty and there is no data! ":$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(),'<br />';
$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();

Run results: 


 The stack is empty 
aa: Brother is in the stack! 
aa1: Brother is in the stack! 
aa1 I'm gone! 
aa2: Brother is in the stack! 
aa3: Brother is in the stack! 
aa4: Brother is in the stack! 
aa4
 The stack is full 
 The stack is full 
aa4 I'm gone! 
aa3 I'm gone! 
aa2 I'm gone! 
aa I'm gone! 
 The stack is empty 
 The stack is empty

Case: Stack-based advanced calculator

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

At this time, we can use the stack algorithm to solve this problem skillfully.

The idea is this: (We use php function substr loop to intercept this string expression, and take out the value of this string in turn, "We have to intercept from the first character", and we set the starting interception position to a variable with cyclic growth, initialized to "$index=0"), You also need to create two stacks, 1 dedicated to storing the number "$numStack", 1 store operator "$operStack", We also need a function that can judge whether it is an operation symbol. Put the intercepted value into this custom function every time, and return an identity that can be distinguished as a number or an operator. By judging this identity, we can determine whether the value is a number or an operator. If it is a number, it will be inserted into the number stack, and if it is an operator, it will be inserted into the symbol stack. If you insert the number stack, you can insert it directly. However, the symbol stack needs special treatment. 1 ["If the symbol stack is empty, insert it directly. Not empty: We want to compare the operation priority of the inserted symbol with the symbol in the stack (we can define a function to determine the symbol priority, assume * and/as 1, and assume + and-as 0, assume that the priority of the operator is higher if the number is larger, so that the operator priority can be obtained). When the priority of the symbol to be inserted is less than or equal to the priority of the operator at the top of the stack, two values are popped from the number stack, and one operator is popped from the symbol stack to operate them. "

The following is an example of php [refer to the php algorithm tutorial from Mr. Han Shunping] 


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

Run results: 


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

PS: Here are some computing tools recommended for your reference in the next step:

On-line 1 yuan function (equation) solution calculation tool;
http://tools.ofstack.com/jisuanqi/equ_jisuanqi

Scientific calculator online _ advanced calculator online calculation:
http://tools.ofstack.com/jisuanqi/jsqkexue

Online Calculator _ Standard Calculator:
http://tools.ofstack.com/jisuanqi/jsq

For more readers interested in PHP related contents, please check the special topics of this site: "Summary of PHP Mathematical Operation Skills", "Summary of PHP Operation and Operator Usage", "Summary of php String (string) Usage", "Encyclopedia of PHP Array (Array) Operation Skills", "Tutorial on PHP Data Structure and Algorithm", "Summary of php Programming Algorithm" and "Summary of php Regular Expression Usage"

I hope this article is helpful to everyone's PHP programming.

Related articles: