表达式求值 博客分类： php 数据结构

 

 

//后缀表达式求值
function calculate($equation = ''){
    if(empty($equation)){
        return 0;
    }
    //声明各个符号的算法函数
    $operations = array('+' => function($param1, $param2){
        return $param1 + $param2;
    }, '-' => function($param1, $param2){
        return $param1 - $param2;
    }, '*' => function($param1, $param2){
        return $param1 * $param2;
    }, '/' => function($param1, $param2){
        return $param1 / $param2;
    });
    //将表达式用空格分隔为数组
    $equationArr = explode(' ', $equation);
    $numStack = array();
    $result = 0;
    //循环数组
    foreach($equationArr as $c){
        //如果是符号
        if(in_array($c, array_keys($operations))){
            $param1 = (int)array_pop($numStack);
            $param2 = (int)array_pop($numStack);
            $subEquation = $operations[$c]($param2, $param1);
            array_push($numStack, $subEquation);
        //如果是数字，将本数入栈
        }else{
            array_push($numStack, intval($c));
        }
    }
    return array_pop($numStack);
}

$result = calculate('2 3 5 7 + - *');
var_dump($result);

 

 

//( ( 1 + 2 ) * 3 ) * 3 + 4 / 2
//转换中缀表达式为后缀表达式
function infixToPosfixNotation($equation = ''){
    if(empty($equation)){
		return false;
	}
    $operations = array('+' => array('p' => 1), '-' => array('p' => 1), '*' => array('p' => 3)
    , '/' => array('p' => 2),'(' => array('p' =>0), ')' => array('p' => 0),
    );
    $numStack = array();
    $operStack = array();
    $equationArr = explode(' ', $equation);
    foreach($equationArr as $c){
        //将优先级高的操作符放到操作符栈顶
        if(in_array($c, array_keys($operations))){
			//如果操作符栈为空
            switch($c){
            case '(':
                array_push($operStack, $c);
                break;
            case ')':
				//如果是右括号
                while(($popOper = end($operStack)) && $popOper != '('){
                    array_push($numStack, array_pop($operStack));
                }
                //去除左括号
                array_pop($operStack);
                break;
            default:
                $popOper = end($operStack);
                while(($popOper = end($operStack)) && $popOper != '(' && $operations[$popOper]['p'] > $operations[$c]['p']){
                    array_push($numStack, array_pop($operStack));
                }//压入符号栈
                array_push($operStack, $c);
                break;
            }         	   
    	}else{
            array_push($numStack, intval($c));
		}
	}
    while($popOper = array_pop($operStack)){
        array_push($numStack, $popOper);
    }
    return implode(' ', $numStack);
}