清华大学韩顺平讲师讲算法之三（上），高性能计算器堆之应用
<html><head><meta http-equiv='content-type' content='text/html;charset=utf-8'><title>/高性能的计算器的结果/</title></head><body><?php//$exp=$_GET['exp'];$exp='3+2*6-2';/*人的眼睛就一条狗老师的思路：1.程序扫描表达式；2。当发现字符是数字则放在数栈里；3。或是运算符，则分以下情况；3。1若符号栈为空则直接入符号栈，3。2如果当前运算符的优先级小于等于版本号栈顶的的运算符的优先级，就开始计算；并便计算结果入数栈；/要补充一下，然后把当前符号入栈改成一直到当前符号的运算级加小于符号栈/3。3若符号栈不为空，如果当前运算符的优先级大于版本号栈顶的的运算符的优先级，就入栈；4。当扫描完毕后，把所有的数弹出，开始计算,最后在数栈里的便是结果。思想要变成代码*///定义一个数据$numsStack=new MyStack();$operStack=new MyStack();$index=0;//是一个扫描标记$keepNum='';//用于拼接数字用的while(true){//依次取出字符$ch=substr($exp,$index,1);if($operStack->isOper($ch) == true){if($operStack->isEmpty()){$operStack->push($ch);}else{//一个函数，运算符的优化级，*/为1；+-为0$operStack->PRI($ch);$stackPRI=$operStack->PRI($operStack->getTop());if($chPRI<=$stackPRI){//2个数栈的数$num1=$numsStack->pop();$num2=$numsStack->pop();//再从符号栈取一个符号$oper=$operStack->pop();$res=$operStack->getResult($num1,$num2,$oper);$numsStack->push($res);//把结果入数栈$operStack->push($ch);//再把符号栈入符栈}}}else{$keepNum.=$ch;//要看一下$ch的下一个是不是数字才能入栈，否则是30+90出错//若到了最后就不用入栈if($index==strlen($exp)-1){$numsStack->push($keepNum);}else{if($operStack->isOper(substr($exp,$index+1,1))){$numsStack->push($keepNum);$keepNum.=$ch;}else{//下一个是数，不做处理}}}$index++;//让$index指向下一个字符//当扫描完毕后，就breakif($index==strlen($exp)){break;//扫描完了}}//只要不空便要计算while (!$operStack->isEmpty()) {$num1=$numsStack->pop();$num2=$numsStack->pop();$oper=$operStack->pop();$res=$operStack->getResult($num1,$num2,$oper);$numsStack->push($res);}//当退出while时，数栈里有一个数，便是结果；//建一个栈栈里增加一个函数public function isOper($ch){if($ch=='-' || $ch=='+' || $ch=='*' || $ch=='/'){return true;}else{return false;}}//isOperpublic function isEmpty(){//是不是空栈if($this->top==-1){return true;}else{return false;}}//isEmptypublic function PRI($ch){if($ch =='*' || $ch=='/'){return 1;}else if($ch == '+' || $ch=='1'){return 0;}}//PRIpublic function getTop(){//返回栈顶元素return $this->thisTop();}public function getResult($num1,$num2,$oper){$res=0;switch ($oper) {case '+':$res=$num1+$num2;break;case '-':$res=$num2-$num1;//顺序break;case '*':$res=$num2*$num1;break;case '/':$res=$num2/$num1;//顺序break;default:# code...break;}}?></body>