清华大学韩顺平讲师讲算法之三（上），高性能计算器堆之应用

webcode

浏览: 5947808 次
性别:
来自: 上海

最近访客更多访客>>

ap950

u012363178

wangyy

ybfjavaeye

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (7533)

社区版块

存档分类

2013-02 ( 78)
2013-01 ( 83)
2012-12 ( 121)
更多存档...

<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指向下一个字符
	//当扫描完毕后，就break
	if($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;
	}
}//isOper
public function isEmpty(){//是不是空栈
	if($this->top==-1){
		return true;
	}else{
		return false;
	}
}//isEmpty
public function PRI($ch){
	if($ch =='*' || $ch=='/'){
		return 1;
	}else if($ch == '+' || $ch=='1'){
		return 0;
	}
}//PRI
public 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>

分享到：