Преобразования алгебраического выражения в постфиксную польскую запись на PHP

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
<?php
/*
() = 0
+- = 10
/* = 20
*/
$s = 'A+B*C+(D+E)/F';
$s = '1+2*3+(4+5)/3'; // =10;
$range['('] = 0;
$range[')'] = 0;
$range['+'] = 10;
$range['-'] = 10;
$range['/'] = 20;
$range['*'] = 20;
$out = '';
$zn = '+-*/';
$isNumeric = preg_match("/\d/",$s);
if ($isNumeric) {
$op = '0123456789';
} else {
$op = 'ABCDEFGHIJKLMNOPRSTUVWXYZ';
}
print("<pre>");
print("\nИсходная строка: \"".$s."\"\n");
$cs = -1;
for ($i=0; $i<strlen($s); $i++)
{
$ch = $s[$i];
if (strpos($op,$ch) !== false) {
$out .= $ch;
}
if ($ch == '(') {
$cs++;
$stack[$cs]['value'] = $ch;
$stack[$cs]['range'] = 0;
}
if (strpos($zn,$ch) !== false) {
while ( ($stack[$cs]['range'] >= $range[$ch]) && ($cs >= 0) )
{
$out .= $stack[$cs]['value'];
$cs--;
}
$stack[++$cs]['value'] = $ch;
$stack[$cs]['range'] = $range[$ch];
}
if ($ch == ')') {
while (($stack[$cs]['value'] != '(' ) && ($cs >= 0))
{
$out .= $stack[$cs]['value'];
unset($stack[$cs]);
$cs--;
}
unset($stack[$cs]);
$cs--;
}
print "\n\n========== Шаг $i =============\n";
print_r('Символ: \''.$ch."'\n");
print_r('Вершина стека: '.$cs."\nСтек: ");
print_r($stack);
print_r("Вывод: ".$out);
print "\n==============================\n\n";
}
while ($cs >= 0) {
if ($stack[$cs]['value'] != '(') {
$out .= $stack[$cs]['value'];
}
$cs--;
}
print("Алгоритм 1:\n".$s."\n");
print($out."\n");
unset($stack);
unset($cs);
// ===================== Алгоритм 2 =========================
$cs = -1;
for ($i=0; $i<strlen($out); $i++)
{
$ch = $out[$i];
if (strpos($op,$ch) !== false) {
$cs++;
$stack[$cs] = $ch;
}
if (strpos($zn,$ch) !== false) {
$n2 = $stack[$cs--];
$n1 = $stack[$cs--];
if ($isNumeric) {
eval('$stack[++$cs] = '.$n1.$ch.$n2.';');
} else {
$stack[++$cs] = '<'.$n1.$ch.$n2.'>';
}
}
}
while ($cs >= 0) {
$out2 .= $stack[$cs];
$cs--;
}
print("\nАлгоритм 2:\n".$out."\n");
print($out2."\n\n");
print("</pre>");
?>