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

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

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

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

<?php
/* =================== 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 == '/')
    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 '/' : return ($n2 / $n1);
    }
}

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

if (empty($expression))
{
    print <<<__eof__
    <form method="post">
    please input the inorder expression :

    <input type="text" size="40" name="expression">
    <input type="submit" value="submit">
    </form>
__eof__;
    exit();
}

$stack_op = null;
$stack_on = null;

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

$len = strlen($expression);

$tmp = '';

for ($i = 0; $i < $len; $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]) <= privority($stack_op->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 <<<__eof__
    the expression { $expression } result is '$result'

    <form method="post">
    if you wan to try again, please input the inorder expression :

    <input type="text" size="40" name="expression" value="$expression">
    <input type="submit" value="submit">
    </form>
__eof__;

?>