用PHP编程计算中序表达式的值

编程

过程: 用class 模拟链表实现堆栈 .:p

完整测试程序地址: http://test.hightman.net/stack/stack_05.php

在表单里可输入: (3+5)/2 之类的表达试，支持 ()+-/*
以下为全部代码

/* =================== Program Description ==================== */
/* Written by MingLian Mar. (hightman) */
/* ============================================================ */

error_reporting(E_ALL & ~E_NOTICE);

if (!defined("NULL"))
define("NULL", 0);

class s_node
{
var $data = NULL;
var $next = NULL;
}

function push(&$stack, $value)
{
$newnode = new s_node;
$newnode->data = $value;
$newnode->next = $stack;

$stack = $newnode;
}

function pop(&$stack, &$value)
{
if ($stack != NULL)
{
$value = $stack->data;
$stack = $stack->next;
}
else
$value = -1;
}

function is_operator($op)
{
return strchr("+-*/()", $op);
}

function privority($op)
{
if ($op == ')' || $op == '(')
return 1;
else if ($op == '+' || $op == '-')
return 2;
else if ($op == '*' || $op == '//m.sbmmt.com/m/')
return 3;
else
return 0;
}

function two_result($op, $n1, $n2)
{
switch ($op)
{
case '+' : return ($n2 + $n1);
case '-' : return ($n2 - $n1);
case '*' : return ($n2 * $n1);
case '//m.sbmmt.com/m/' : return ($n2 / $n1);
}
}

// main program
$expression = trim($_POST['expression']);

if (empty($expression))
{
print

$stack_op = NULL;
$stack_on = NULL;

$n1 = $n2 = 0;
$op = '';

$len = strlen($expression);

$tmp = '';

for ($i = 0; $i {
if (is_operator($expression[$i]))
{
$tmp = trim($tmp);
if (!empty($tmp))
{
push($stack_on, $tmp);
$tmp = '';
}

if ($expression[$i] == '(' || empty($stack_op))
push($stack_op, $expression[$i]);
else if ($expression[$i] == ')')
{
while ($stack_op->data != '(')
{
pop($stack_on, $n1);
pop($stack_on, $n2);
pop($stack_op, $op);

push($stack_on, two_result($op, $n1, $n2));
}

pop($stack_op, $op); // pop the '('
}
else {
while (privority($expression[$i]) data))
{
pop($stack_on, $n1);
pop($stack_on, $n2);
pop($stack_op, $op);

push($stack_on, two_result($op, $n1, $n2));
}
push($stack_op, $expression[$i]);
}
}
else
$tmp .= $expression[$i];
}

$tmp = trim($tmp);
if (!empty($tmp))
{
push($stack_on, $tmp);
$tmp = '';
}

while (!empty($stack_op))
{
pop($stack_op, $op);
pop($stack_on, $n1);
pop($stack_on, $n2);

push($stack_on, two_result($op, $n1, $n2));
}

$result = 0;
pop($stack_on, $result);

print The expression { $expression } result is '$result'

?>