1 <?php
  2 //栈的应用 表达式求值：3+2*6-2
  3 class Stack
  4 {
  5     private $top=-1;//默认是-1, 表示该栈是空的
  6     private $max_size = 100;//栈的最大容量
  7     private $stack = array();
  8     
  9     /**
 10      * 入栈
 11      */
 12     public function push($val)
 13     {
 14         if($this->top == $this->max_size-1)//栈满
 15         {
 16             return false;
 17         }
 18         $this->top++;
 19         $this->stack[$this->top] = $val;
 20     }
 21     
 22     /**
 23      * 出栈
 24      */
 25     public function pop()
 26     {
 27         if($this->top == -1)//栈空
 28         {
 29             return false;
 30         }
 31         $value = $this->stack[$this->top];
 32         $this->top--;
 33         return $value;
 34     }
 35     
 36     /**
 37      * 取栈顶元素
 38      */
 39     public function get_top()
 40     {
 41         if($this->top == -1)
 42         {
 43             return false;
 44         }
 45         return $this->stack[$this->top];//返回栈顶的元素，只取，但是不出栈
 46     }
 47     
 48     /**
 49      * 判断是否为空栈
 50      */
 51     public function is_empty()
 52     {
 53         if($this->top == -1)
 54         {
 55             return true;
 56         } else {
 57             return false;
 58         }
 59     }
 60     
 61     /**
 62      * 判断是不是一个运算符
 63      */
 64     public function is_oper($ch)
 65     {
 66         if($ch==‘+‘ || $ch==‘-‘ || $ch==‘*‘ || $ch==‘/‘)
 67         {
 68             return 1;
 69         } else {
 70             return 0;
 71         }
 72     }
 73     
 74     /**
 75      * 判断运算符的优先级
 76      * *和/为1 +和-为0 括号后面改进
 77      */
 78     public function PRI($ch)
 79     {
 80         if($ch==‘*‘ || $ch==‘/‘)
 81         {
 82             return 1;
 83         } else if($ch==‘+‘ || $ch==‘-‘){
 84             return 0;
 85         }
 86     }
 87     
 88     /**
 89      * 计算的函数
 90      */
 91     public function get_result($num1, $num2, $oper)
 92     {
 93         $res = 0;
 94         switch($oper){
 95             case ‘+‘:
 96                 $res = $num1 + $num2;
 97                 break;
 98             case ‘-‘:
 99                 $res = $num2 - $num1;//注意顺序
100                 break;
101             case ‘*‘:
102                 $res = $num1 * $num2;
103                 break;
104             case ‘/‘:
105                 $res = $num2 / $num1;//注意顺序
106                 break;
107         }
108         return $res;
109     }
110 }
111 
112 /**
113  * 计算(参数校验省略)
114  */
115 function calculator($operStack, $numsStack, $exp)
116 {
117     $index = 0;//$index就是一个扫描标记
118     $len = strlen($exp);
119     $nums = ‘‘;//用于拼接多位数的字符串
120     while(true)
121     {
122         $ch = substr($exp, $index, 1);//从$exp里的$index位置取出一个字符
123         $is_oper = $operStack->is_oper($ch);
124         if($is_oper)//判断$ch是不是运算符
125         {
126             //说明是运算符
127             /**
128              * 1.如果符号栈为空，就直接入栈；
129              * 2.如果符号栈不为空，如果当前运算符的优先级小于等于符号栈顶运算符的优先级，就计算，并把计算结果入数栈，
130              *   然后把当前符号入符号栈；
131              * 3.如果符号栈不为空，如果当前运算符的优先级大于符号栈顶运算符的优先级，就入栈
132              */
133             if($operStack->is_empty())
134             {
135                 $operStack->push($ch);
136             } else {
137                 //判断当前符号跟栈顶符号的运算符优先级
138                 $chPRI = $operStack->PRI($ch);
139                 //只要你准备入符号栈的运算优先级小于等于当前栈栈顶的运算优先级，就一直计算
140                 //直到这个条件不满足，才把当前的符号入符号栈
141                 //并且只要符号栈不为空
142                 while(!$operStack->is_empty() && $chPRI<=$operStack->PRI($operStack->get_top()))//处理2*7-3*5-3这种情况
143                 {
144                     //计算
145                     //从数栈里面依次出两个数
146                     $num1 = $numsStack->pop();
147                     $num2 = $numsStack->pop();
148                     
149                     //再从符号栈里取出一个运算符
150                     $oper = $operStack->pop();
151                     $res = $operStack->get_result($num1, $num2, $oper);
152                     
153                     //$res入栈  当前操作符入栈
154                     $numsStack->push($res);
155                 }
156                 $operStack->push($ch);
157             }
158         } else {
159             $nums .= $ch;//处理多位数字
160             //判断数字是否是最后一个，是：直接入栈；否：接着判断下一个字符是否是数字
161             if($index == $len-1)
162             {
163                 $numsStack->push($nums);
164             } else {
165                 //判断下一个字符是否是数字
166                 if($operStack->is_oper(substr($exp, $index+1, 1)))
167                 {
168                     $numsStack->push($nums);
169                     $nums = ‘‘;//置空
170                 }
171             }
172         }
173         $index++;//让$index指向下一个字符
174         if($index == $len)//判断是否扫码完毕
175         {
176             break;//当扫描完毕后，就break
177         }
178     }
179     
180     /**
181      * 4.当扫描完毕后，就依次弹出数栈和符号栈的数据，并计算，最终留在数栈的值，就是运算结果
182      */
183     while(!$operStack->is_empty())
184     {
185         $num1 = $numsStack->pop();
186         $num2 = $numsStack->pop();
187         $oper = $operStack->pop();
188         $res = $operStack->get_result($num1, $num2, $oper);
189         $numsStack->push($res);
190     }
191     
192     return $numsStack->get_top();
193 }
194 
195 $exp = "7*2-5*3-3";
196 $exp = "30+20*6-80";
197 $exp = "3+2*6-4";
198 $numsStack = new Stack();
199 $operStack = new Stack();
200 $res = calculator($operStack, $numsStack, $exp);
201 
202 var_dump($res);