梦游时光互联客服中心 - 服务器合租/整机租用 - 用PHP编程计算中序表达式的值 (用class 模拟链表实现堆栈 .:p)

本帖主题: 用PHP编程计算中序表达式的值 (用class 模拟链表实现堆栈 .:p)

↓

SinaViVi

Friend

2006-8-8 11:36 PM No.1

发表人：ttmax 社区短消息 TOP

ttmax (瘟神)
King
Rank: 6

洪魔！天下无双

UID 1330
精华 5
积分 1630
帖子 1146
体力 1121
威望 99
贡献 0
阅读权限 70
注册 2006-6-18
状态离线

[广告]: 新手解疑1：FTP空间各文件目录的作用

完整测试程序:
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__;

?>