当前位置：首页 → 问答吧 → 逆波兰表达式计算

逆波兰表达式计算

时间：2011-12-16

来源：互联网

最近在整理资料时发现了一些以前收藏的有趣代码
计划逐步将他们移植到 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

作者: xuzuning 发布时间: 2011-12-16

该回复于2011-12-16 09:42:24被管理员删除

对我有用[0]
丢个板砖[0]
引用
举报
管理
TOP

xiachao2008
(xxx)
等　级：

#2楼得分：0回复于：2011-12-16 09:36:17

先回贴在看

作者: bl1988530 发布时间: 2011-12-16

程序有错误给。

HTML code


( ! ) Notice: Undefined variable: t in D:\php\easyphp\www\person_php\other\a.php on line 40 
Call Stack 
# Time Memory Function Location 
1 0.0010 354696 {main}( ) ..\a.php:0 
2 0.0010 354752 postfix( $infix = &apos;(2+3)*(3+4)&apos; ) ..\a.php:78 
Dump $_SERVER 
$_SERVER['REMOTE_ADDR'] =
 string '127.0.0.1' (length=9)

 
$_SERVER['REQUEST_METHOD'] =
 string 'GET' (length=3)

 
$_SERVER['REQUEST_URI'] =
 string '/person_php/other/a.php' (length=23)

 
Variables in local scope (#2) 
$data =
 array
  empty

 
$i =
 int 1

 
$infix =
 string '(2+3)*(3+4)' (length=11)

 
$last =
 int -1

 
$len =
 int 11

 
$priority =
 array
  '+' => int 1
  '-' => int 1
  '*' => int 2
  '/' => int 2
  '(' => int 0
  ')' => int 0
  '.' => int 0
  0 => int 0
  1 => int 0
  2 => int 0
  3 => int 0
  4 => int 0
  5 => int 0
  6 => int 0
  7 => int 0
  8 => int 0
  9 => int 0

 
$stack =
 array
  0 => string '(' (length=1)

 
$t =
 Undefined 
$top =
 int 0

 

( ! ) Notice: Undefined variable: t in D:\php\easyphp\www\person_php\other\a.php on line 44 
Call Stack 
# Time Memory Function Location 
1 0.0010 354696 {main}( ) ..\a.php:0 
2 0.0010 354752 postfix( $infix = &apos;(2+3)*(3+4)&apos; ) ..\a.php:78 
Variables in local scope (#2) 
$data =
 array
  empty

 
$i =
 int 1

 
$infix =
 string '(2+3)*(3+4)' (length=11)

 
$last =
 int -1

 
$len =
 int 11

 
$priority =
 array
  '+' => int 1
  '-' => int 1
  '*' => int 2
  '/' => int 2
  '(' => int 0
  ')' => int 0
  '.' => int 0
  0 => int 0
  1 => int 0
  2 => int 0
  3 => int 0
  4 => int 0
  5 => int 0
  6 => int 0
  7 => int 0
  8 => int 0
  9 => int 0

 
$stack =
 array
  0 => string '(' (length=1)

 
$t =
 Undefined 
$top =
 int 0

 

( ! ) Notice: Undefined offset: 0 in D:\php\easyphp\www\person_php\other\a.php on line 26 
Call Stack 
# Time Memory Function Location 
1 0.0010 354696 {main}( ) ..\a.php:0 
2 0.0010 354752 postfix( $infix = &apos;(2+3)*(3+4)&apos; ) ..\a.php:78 
Variables in local scope (#2) 
$data =
 array
  0 => int 5

 
$i =
 int 5

 
$infix =
 string '(2+3)*(3+4)' (length=11)

 
$last =
 int 3

 
$len =
 int 11

 
$priority =
 array
  '+' => int 1
  '-' => int 1
  '*' => int 2
  '/' => int 2
  '(' => int 0
  ')' => int 0
  '.' => int 0
  0 => int 0
  1 => int 0
  2 => int 0
  3 => int 0
  4 => int 0
  5 => int 0
  6 => int 0
  7 => int 0
  8 => int 0
  9 => int 0

 
$stack =
 array
  empty

 
$t =
 string '' (length=0)

 
$top =
 int 0

 

( ! ) Notice: Undefined index: in D:\php\easyphp\www\person_php\other\a.php on line 26 
Call Stack 
# Time Memory Function Location 
1 0.0010 354696 {main}( ) ..\a.php:0 
2 0.0010 354752 postfix( $infix = &apos;(2+3)*(3+4)&apos; ) ..\a.php:78 
Variables in local scope (#2) 
$data =
 array
  0 => int 5

 
$i =
 int 5

 
$infix =
 string '(2+3)*(3+4)' (length=11)

 
$last =
 int 3

 
$len =
 int 11

 
$priority =
 array
  '+' => int 1
  '-' => int 1
  '*' => int 2
  '/' => int 2
  '(' => int 0
  ')' => int 0
  '.' => int 0
  0 => int 0
  1 => int 0
  2 => int 0
  3 => int 0
  4 => int 0
  5 => int 0
  6 => int 0
  7 => int 0
  8 => int 0
  9 => int 0

 
$stack =
 array
  empty

 
$t =
 string '' (length=0)

 
$top =
 int 0

 
35

作者: xiachao2008 发布时间: 2011-12-16

这个好东西。

作者: xiachao2008 发布时间: 2011-12-16

逆波兰表达式计算

热门阅读

热门下载