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
123
124
| <?php
define('DEBUG', ($argc - 1) > 0 ? 1 : 0);
$handle = fopen('php://stdin', 'r');
echo 'Enter N (natural, even) = ';
while (!($n = intval(fgets($handle))) or ($n % 2)) {}
$radix = 2 + ($n/2 - 1) * 2;
/*
$radix - основание системы, в которой будет формироваться
числовое представления скобочного выражения.
Код 0 имеют пустота в выражении.
Коды 1 и 2 соответсвуют пустым скобкам [] и () (без
аргументов).
Код 1 + 2 * n имеют скобки [] с n аргументами
(т. е. с арностью n).
Код 2 + 2 * n имеют скобки () с n аргументами.
*/
$out = fopen('output.txt', 'w');
/* выч-е макс. кода для Nзначного выражения.
этим исключ. часть заведомо неправильных
выражений (напр., ...3, ...4, ...4_1 и т. п.) */
$imax = 0;
$w = 1;
$i = 0;
for (; $i < ($n / 2 - 1); ++$i, $w *= $radix)
$imax += 4 * $w;
$imax += 2 * $w;
// переменные для отображения прогресса
$pcnt = 0;
$pcnt_incr = 100 / $imax;
$done = 0;
$exprs = 0;
$jmax = pow($radix, $n/2 - 1);
// перебор кодов всех возможных выражений
for ($i = 1; $i <= $imax; $i++, $pcnt += $pcnt_incr) {
//отображение прогресса в %
if ($pcnt >= 5) {
$done += 5 * floor($pcnt / 5);
$pcnt = $pcnt % 5;
echo "~{$done}% done\n";
}
if (DEBUG) echo "i (no.) = {$i}\n";
$expr = array();
$ii = $i;
$arity = 0; /*максимально допустимая арность следующих
скобок */
//вынесено за пределы цикла т. к. по сути = const
//$jmax = $j = pow($radix, $n/2 - 1);
for ($j = $jmax; $j > 0; $j = floor($j / $radix)) {
if (DEBUG) echo "j (weight) = {$j}\n";
//$t - тип (код) скобок
if ($t = floor($ii / $j)) {
/*данные скобки имеют недопустимую, с учетом уже
обработанной части выражения, арность*/
if ($t > 2 and ($this_arity = ceil(($t - 2)/2)) > $arity) {
if (DEBUG) echo "Arity is too high\n";
continue 2;
}
$ii %= $j;
/*пустые скобки увеличивают максимальную арность
следующих скобок*/
if ($t < 3) ++$arity;
/*скобки с ненулевой арностью уменьшают максимальную
арность следующих скобок на собственную арность
минус 1*/
else $arity -= $this_arity - 1;
} else if ($arity) {
if (DEBUG) echo "Unexpected space\n";
continue 2; /* Пустота допустима
только на конце выражения (для реализации выражений
короче чем N)*/
}
if (DEBUG) "t (brackets' type) = {$t}\n";
array_unshift($expr, $t);
}
if (DEBUG) {
echo 'Press ENTER to continue...';
fgets($handle);
echo 'Expression added, code = '
. implode(" ", $expr) . "\n";
}
write_expr($expr);
++$exprs;
}
echo "100% done\n";
echo 'Expressions generated: ' . $exprs . "\n";
function write_expr($expr) {
global $out;
$str = '';
$stack = array(); //стек для скобок с ненулевой арностью
for ($i = 0, $imax = count($expr); $i < $imax; $i++) {
if (!$expr[$i]) break;
$brackets = $expr[$i] & 1 ? '[]' : '()';
if ($expr[$i] > 2) {
array_unshift($stack,
array(
ceil(($expr[$i] - 2)/2),
$brackets[1]
)
);
$str .= $brackets[0];
} else {
$str .= $brackets;
while (count($stack) and !--$stack[0][0]) {
$str .= $stack[0][1];
array_shift($stack);
}
}
}
fputs($out, (DEBUG ? implode(' ', $expr) . ': ' : '') . "{$str}\n");
}
fclose($handle);
?> |
(
