[原创] 用PHP编程计算中序表达式的值

hightman

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

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

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

1. 
   
2. <?php
   
3. /* =================== Program Description ==================== */
   
4. /* Written by MingLian Mar. (hightman)                          */
   
5. /* ============================================================ */
   
6. 
   
7. error_reporting(E_ALL & ~E_NOTICE);
   
8. 
   
9. if (!defined("NULL"))
   
10.     define("NULL", 0);
    
11. 
    
12. class s_node
    
13. {
    
14.     var $data = NULL;
    
15.     var $next = NULL;
    
16. }
    
17. 
    
18. 
    
19. function push(&$stack, $value)
    
20. {
    
21.     $newnode = new s_node;
    
22.     $newnode->;data = $value;
    
23.     $newnode->;next = $stack;
    
24. 
    
25.     $stack = $newnode;
    
26. }
    
27. 
    
28. function pop(&$stack, &$value)
    
29. {
    
30.     if ($stack != NULL)
    
31.     {
    
32.     $value = $stack->;data;
    
33.     $stack = $stack->;next;
    
34.     }
    
35.     else
    
36.     $value = -1;
    
37. }
    
38. 
    
39. function is_operator($op)
    
40. {
    
41.     return strchr("+-*/()", $op);
    
42. }
    
43. 
    
44. function privority($op)
    
45. {
    
46.     if ($op == ')' || $op == '(')
    
47.     return 1;
    
48.     else if ($op == '+' || $op == '-')
    
49.     return 2;
    
50.     else if ($op == '*' || $op == '/')
    
51.     return 3;
    
52.     else
    
53.     return 0;
    
54. }
    
55. 
    
56. function two_result($op, $n1, $n2)
    
57. {
    
58.     switch ($op)
    
59.     {
    
60.     case '+' : return ($n2 + $n1);
    
61.     case '-' : return ($n2 - $n1);
    
62.     case '*' : return ($n2 * $n1);
    
63.     case '/' : return ($n2 / $n1);
    
64.     }
    
65. }
    
66. 
    
67. // main program
    
68. $expression = trim($_POST['expression']);
    
69. 
    
70. if (empty($expression))
    
71. {
    
72.     print <<<__EOF__
    
73.     <form method="post">;
    
74.     Please input the inorder expression :
    
75. 
    
76.     <input type="text" size="40" name="expression">;
    
77.     <input type="submit" value="submit">;
    
78.     </form>;
    
79. __EOF__;
    
80.     exit();
    
81. }
    
82. 
    
83. $stack_op = NULL;
    
84. $stack_on = NULL;
    
85. 
    
86. $n1 = $n2 = 0;
    
87. $op = '';
    
88. 
    
89. $len = strlen($expression);
    
90. 
    
91. $tmp = '';
    
92. 
    
93. for ($i = 0; $i < $len; $i++)
    
94. {
    
95.     if (is_operator($expression[$i]))
    
96.     {
    
97.     $tmp = trim($tmp);
    
98.     if (!empty($tmp))
    
99.     {
    
100.         push($stack_on, $tmp);
     
101.         $tmp = '';
     
102.     }
     
103. 
     
104.     if ($expression[$i] == '(' || empty($stack_op))
     
105.         push($stack_op, $expression[$i]);
     
106.     else if ($expression[$i] == ')')
     
107.     {
     
108.         while ($stack_op->;data != '(')
     
109.         {
     
110.         pop($stack_on, $n1);
     
111.         pop($stack_on, $n2);
     
112.         pop($stack_op, $op);
     
113. 
     
114.         push($stack_on, two_result($op, $n1, $n2));
     
115.         }
     
116. 
     
117.         pop($stack_op, $op); // pop the '('
     
118.     }
     
119.     else {
     
120.         while (privority($expression[$i]) <= privority($stack_op->;data))
     
121.         {
     
122.         pop($stack_on, $n1);
     
123.         pop($stack_on, $n2);
     
124.         pop($stack_op, $op);
     
125. 
     
126.         push($stack_on, two_result($op, $n1, $n2));
     
127.         }
     
128.         push($stack_op, $expression[$i]);
     
129.     }
     
130.     }
     
131.     else
     
132.     $tmp .= $expression[$i];
     
133. }
     
134. 
     
135. $tmp = trim($tmp);
     
136. if (!empty($tmp))
     
137. {
     
138.     push($stack_on, $tmp);
     
139.     $tmp = '';
     
140. }
     
141. 
     
142. while (!empty($stack_op))
     
143. {
     
144.     pop($stack_op, $op);
     
145.     pop($stack_on, $n1);
     
146.     pop($stack_on, $n2);
     
147. 
     
148.     push($stack_on, two_result($op, $n1, $n2));
     
149. }
     
150. 
     
151. $result = 0;
     
152. pop($stack_on, $result);
     
153. 
     
154. print <<<__EOF__
     
155.     The expression { $expression } result is '$result'
     
156. 
     
157.     <form method="post">;
     
158.     If you wan to try again, Please input the inorder expression :
     
159. 
     
160.     <input type="text" size="40" name="expression" value="$expression">;
     
161.     <input type="submit" value="submit">;
     
162.     </form>;
     
163. __EOF__;
     
164. 
     
165. ?>;
     

复制代码

夜猫子

建议以后用[code][/code]来显示代码，这样可以保留代码的缩进，方便浏览

hightman

sorry, 初次发贴，已经修正．

夜猫子

>;初次驾到
自称“架到”似乎不符合中国人的习惯吧，呵呵，我是书呆子，有时喜欢咬文嚼字，欢迎大驾光临。

hightman

再次sorry.  //blush