当前位置: 代码迷 >> PHP >> 逆波兰表达式计算,该如何解决
  详细解决方案

逆波兰表达式计算,该如何解决

热度:448   发布时间:2012-02-13 17:20:26.0
逆波兰表达式计算
最近在整理资料时发现了一些以前收藏的有趣代码
计划逐步将他们移植到 PHP 供有兴趣的人参考
PHP code
/**
 * 逆波兰表达式计算
 * 中缀转后缀
 **/
function postfix($infix) {
    $priority = array( //算符优先级
        '+' => 1, '-' => 1,
        '*' => 2, '/' => 2,
        '(' => 0, ')' => 0,
        '.' => 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
        );
    $stack = array(); //符号栈
    $data = array(); //数值栈 
    $i = $top = 0;
    $last = -1;
    $len = strlen($infix);
    while($i<$len) {
        switch($infix{$i}) {
            case '(':
                array_unshift($stack, $infix{$i});
                break;
            case '+': case '-': case '*': case '/':
                if($t != '') array_unshift($data, $t);
                $t = '';
                while($priority[$stack[0]] >= $priority[$infix{$i}]) {
                    postfix_callback(array_shift($stack), $data);
                }
                array_unshift($stack, $infix{$i});
                break;
            case ')':
                if($t != '') array_unshift($data, $t);
                $t = '';
                while($stack[0] != '(') {
                    postfix_callback(array_shift($stack), $data);
                }
                array_shift($stack);
                break;
            default:
                if($i > $last+1 && $t != '') {
                    array_unshift($data, $t);
                    $t = '';
                }
                $t .= $infix{$i};
                $last = $i;
                break; 
        }
        $i++;
    }
    while($stack) {
        postfix_callback(array_shift($stack), $data);
    }
    return $data[0];
}

/**
 * postfix 的工作函数
 * 用于计算表达式的值
 **/
function postfix_callback($ch, &$data) {
    $b = array_shift($data);
    switch($ch) {
        case '+':
            $data[0] += $b;
            break;
        case '-':
            $data[0] -= $b;
            break;
        case '*':
            $data[0] *= $b;
            break;
        case '/':
            $data[0] /= $b;
            break;
    }
}

测试例
PHP code
echo postfix( '(2+3)*(3+4)' ); //out 35


------解决方案--------------------
先回贴在看
------解决方案--------------------
这个好东西。

------解决方案--------------------
前排占座, 板主老大给力.
------解决方案--------------------
前排占座, 板主老大给力.
  相关解决方案