homo/
lib.rs

1//! This crate is a Rust port of [homo].
2//!
3//! [homo]: https://github.com/itorr/homo
4
5#[cfg(test)]
6mod tests;
7
8use std::borrow::Cow;
9use std::cmp::Ordering;
10use std::sync::LazyLock;
11
12use pomsky_macro::pomsky;
13use regex::{Captures, Regex};
14pub use uint::FromDecStrErr;
15use uint::construct_uint;
16
17// 匹配 *(1) 或 +(0) 冗余运算
18static RE01: LazyLock<Regex> = LazyLock::new(|| Regex::new(pomsky!("*(1)" | "+(0)" End)).unwrap());
19// 匹配数字
20static RE_DIGITS: LazyLock<Regex> = LazyLock::new(|| Regex::new(pomsky!([digit]+)).unwrap());
21static RE乘除冗余括号: LazyLock<Regex> =
22    LazyLock::new(|| Regex::new(pomsky!(:(["*/"]) '(' :(!["+-()"]+) ')')).unwrap());
23static RE加减冗余括号: LazyLock<Regex> =
24    LazyLock::new(|| Regex::new(pomsky!(:(["+-"]) '(' :(!["()"]+) ')' :(["+-"]))).unwrap());
25static RE行末加减冗余括号: LazyLock<Regex> =
26    LazyLock::new(|| Regex::new(pomsky!(:(["+-"]) '(' :(!["()"]+) ')' End)).unwrap());
27static RE行冗余括号: LazyLock<Regex> =
28    LazyLock::new(|| Regex::new(pomsky!(Start '(' :(!["()"]+) ')' End)).unwrap());
29// 基础 114514 算式
30const MEMO: &[(u32, &str); 520] = &[
31    (0, "(1-1)*4514"),
32    (1, "11/(45-1)*4"),
33    (2, "-11+4-5+14"),
34    (3, "11*-4+51-4"),
35    (4, "-11-4+5+14"),
36    (5, "11-4*5+14"),
37    (6, "1-14+5+14"),
38    (7, "11-4+5-1-4"),
39    (8, "11-4+5/1-4"),
40    (9, "11-4+5+1-4"),
41    (10, "-11/4+51/4"),
42    (11, "11*-4+51+4"),
43    (12, "-11+4+5+14"),
44    (13, "1*14-5/1+4"),
45    (14, "11+4-5/1+4"),
46    (15, "1+14-5+1+4"),
47    (16, "11-4-5+14"),
48    (17, "11+4*5-14"),
49    (18, "1+1+4*5*1-4"),
50    (19, "1+1+4*5+1-4"),
51    (20, "-11+45-14"),
52    (21, "-1-1+4+5+14"),
53    (22, "1*14+5-1+4"),
54    (23, "1*14-5+14"),
55    (24, "1+14-5+14"),
56    (25, "11*4-5-14"),
57    (26, "11-4+5+14"),
58    (27, "11+4*5/1-4"),
59    (28, "11+4*5+1-4"),
60    (29, "-11+45-1-4"),
61    (30, "1*-1+45-14"),
62    (31, "1/1*45-14"),
63    (32, "1*1+45-14"),
64    (33, "1+1+45-14"),
65    (34, "1-14+51-4"),
66    (35, "11*4+5-14"),
67    (36, "11+4*5+1+4"),
68    (37, "-11+45-1+4"),
69    (38, "-11+45*1+4"),
70    (39, "-11+45+1+4"),
71    (40, "-11+4*51/4"),
72    (41, "1/1*45*1-4"),
73    (42, "11+45-14"),
74    (43, "1+1*45+1-4"),
75    (44, "114-5*14"),
76    (45, "11+4*5+14"),
77    (46, "11*4+5+1-4"),
78    (47, "1/-1+45-1+4"),
79    (48, "-11+45+14"),
80    (49, "1*1*45/1+4"),
81    (50, "1+1*45/1+4"),
82    (51, "11+45-1-4"),
83    (52, "11+45/1-4"),
84    (53, "11+45+1-4"),
85    (54, "11-4+51-4"),
86    (55, "-1+14*5-14"),
87    (56, "1*14*5-14"),
88    (57, "1+14*5-14"),
89    (58, "-1+1*45+14"),
90    (59, "114-51-4"),
91    (60, "11+45*1+4"),
92    (61, "1+1+45+14"),
93    (62, "1+14+51-4"),
94    (63, "11*4+5+14"),
95    (64, "11*4+5*1*4"),
96    (65, "1*14*5-1-4"),
97    (66, "1*14*5-1*4"),
98    (67, "1-1*4+5*14"),
99    (68, "1+1-4+5*14"),
100    (69, "1*14+51+4"),
101    (70, "11+45+14"),
102    (71, "(1+14)*5-1*4"),
103    (72, "-1-1+4+5*14"),
104    (73, "1*14*5-1+4"),
105    (74, "1/1*4+5*14"),
106    (75, "1+14*5*1+4"),
107    (76, "1+1+4+5*14"),
108    (77, "11-4+5*14"),
109    (78, "(1+1)*4+5*14"),
110    (79, "1*-1+4*5/1*4"),
111    (80, "1-1+4*5*1*4"),
112    (81, "1/1+4*5*1*4"),
113    (82, "1+1+4*5/1*4"),
114    (83, "-1+14+5*14"),
115    (84, "1*14+5*14"),
116    (85, "1+14+5*14"),
117    (86, "(1+1)*45*1-4"),
118    (87, "11+4*(5+14)"),
119    (88, "1*14*(5+1)+4"),
120    (89, "(1+14)*5+14"),
121    (90, "-114+51*4"),
122    (91, "11*4+51-4"),
123    (92, "(1+1)*(45-1)+4"),
124    (93, "(1+1)*45-1+4"),
125    (94, "114-5/1*4"),
126    (95, "114-5-14"),
127    (96, "11*(4+5)+1-4"),
128    (97, "1+1*4*(5+1)*4"),
129    (98, "1+1+4*(5+1)*4"),
130    (99, "11*4+51+4"),
131    (100, "1*(1+4)*5*1*4"),
132    (101, "1+1*4*5*(1+4)"),
133    (102, "11*(4+5)-1+4"),
134    (103, "11*(4+5)+1*4"),
135    (104, "114-5-1-4"),
136    (105, "114+5-14"),
137    (106, "114-5+1-4"),
138    (107, "11-4*-(5+1)*4"),
139    (110, "-(11-451)/4"),
140    (111, "11+4*5*(1+4)"),
141    (112, "114-5-1+4"),
142    (113, "114-5/1+4"),
143    (114, "11*4+5*14"),
144    (115, "114+5*1-4"),
145    (116, "114+5+1-4"),
146    (117, "(1-14)*(5-14)"),
147    (118, "(1+1)*(45+14)"),
148    (120, "-(1+1)*4*5*(1-4)"),
149    (121, "11*(45-1)/4"),
150    (122, "114+5-1+4"),
151    (123, "114-5+14"),
152    (124, "114+5+1+4"),
153    (125, "-1-14*(5-14)"),
154    (126, "1*(14-5)*14"),
155    (127, "1-14*(5-14)"),
156    (128, "1+1+(4+5)*14"),
157    (129, "114+5*-(1-4)"),
158    (130, "-1+145-14"),
159    (131, "1*145-14"),
160    (132, "1+145-14"),
161    (133, "114+5+14"),
162    (134, "114+5/1*4"),
163    (135, "-1/1*45*(1-4)"),
164    (136, "1*1-45*(1-4)"),
165    (137, "1+1-45*(1-4)"),
166    (138, "-1*(1+45)*(1-4)"),
167    (139, "-1+145-1-4"),
168    (140, "1*145-1-4"),
169    (141, "1+145-1-4"),
170    (142, "1+145*1-4"),
171    (143, "1+145+1-4"),
172    (146, "11+45*-(1-4)"),
173    (147, "-1+145-1+4"),
174    (148, "1*145-1+4"),
175    (149, "1*145*1+4"),
176    (150, "1+145*1+4"),
177    (151, "1+145+1+4"),
178    (152, "(1+1)*4*(5+14)"),
179    (154, "11*(4-5)*-14"),
180    (157, "1*(1-4)*-51+4"),
181    (158, "-1+145+14"),
182    (159, "1*145+14"),
183    (160, "1+145+14"),
184    (161, "114+51-4"),
185    (165, "11*-45/(1-4)"),
186    (168, "(11+45)*-(1-4)"),
187    (169, "114+51+4"),
188    (170, "(11-45)*-(1+4)"),
189    (171, "114*(5+1)/4"),
190    (172, "11*4*(5-1)-4"),
191    (174, "-1-1+(45-1)*4"),
192    (175, "-1+1*(45-1)*4"),
193    (176, "1*1*(45-1)*4"),
194    (177, "1+1*(45-1)*4"),
195    (178, "-1-1+45*1*4"),
196    (179, "-1/1+45*1*4"),
197    (180, "1*1*45*1*4"),
198    (181, "1+1*45*1*4"),
199    (182, "1+1+45/1*4"),
200    (183, "-1+1*(45+1)*4"),
201    (184, "114+5*14"),
202    (185, "1-1*-(45+1)*4"),
203    (186, "1+1+(45+1)*4"),
204    (187, "1/-1+4*(51-4)"),
205    (188, "1-1-(4-51)*4"),
206    (189, "-11-4+51*4"),
207    (190, "1*-14+51*4"),
208    (191, "1-14+51*4"),
209    (192, "(1+1)*4*(5+1)*4"),
210    (195, "(1-14)*5*(1-4)"),
211    (196, "-(1+1)*4+51*4"),
212    (197, "-11+4+51*4"),
213    (198, "-1-1+4*51-4"),
214    (199, "1*-1+4*51-4"),
215    (200, "1/1*4*51-4"),
216    (201, "1/1-4+51*4"),
217    (202, "1+1-4+51*4"),
218    (204, "(1-1)/4+51*4"),
219    (206, "11*4*5-14"),
220    (207, "-1+1*4*51+4"),
221    (208, "1*1*4+51*4"),
222    (209, "1+1*4*51+4"),
223    (210, "1+1+4+51*4"),
224    (211, "11-4+51*4"),
225    (212, "(1+1)*4+51*4"),
226    (214, "-11+45*(1+4)"),
227    (215, "11*4*5-1-4"),
228    (216, "11*4*5-1*4"),
229    (217, "11*4*5+1-4"),
230    (218, "1*14+51*4"),
231    (219, "1+14+51*4"),
232    (220, "1*1*(4+51)*4"),
233    (221, "1/1+4*(51+4)"),
234    (222, "1+1+4*(51+4)"),
235    (223, "11*4*5-1+4"),
236    (224, "11*4*5/1+4"),
237    (225, "11*4*5+1+4"),
238    (226, "1*1+45*(1+4)"),
239    (227, "1+1+45*(1+4)"),
240    (229, "1145/(1+4)"),
241    (230, "1*(1+45)*(1+4)"),
242    (231, "11+4*(51+4)"),
243    (234, "11*4*5+14"),
244    (235, "1*(1+4)*(51-4)"),
245    (236, "11+45*(1+4)"),
246    (240, "(11+4)*(5-1)*4"),
247    (247, "-(1-14)*(5+14)"),
248    (248, "11*4+51*4"),
249    (251, "1*-(1+4)*-51-4"),
250    (252, "(114-51)*4"),
251    (257, "(1+1)/4*514"),
252    (259, "1*(1+4)*51+4"),
253    (260, "1*(14+51)*4"),
254    (265, "-1+14*(5+14)"),
255    (266, "1*14*(5+14)"),
256    (267, "1+14*(5+14)"),
257    (268, "11*4*(5+1)+4"),
258    (269, "-11+4*5*14"),
259    (270, "(1+1)*45*-(1-4)"),
260    (275, "1*(1+4)*(51+4)"),
261    (278, "-1-1+4*5*14"),
262    (279, "1*-1+4*5*14"),
263    (280, "1-1+4*5*14"),
264    (281, "1+14*5/1*4"),
265    (282, "1+1+4*5*14"),
266    (285, "(11+4)*(5+14)"),
267    (286, "(1145-1)/4"),
268    (291, "11+4*5*14"),
269    (297, "-11*(4+5)*(1-4)"),
270    (300, "(11+4)*5/1*4"),
271    (312, "(1-14)*-(5+1)*4"),
272    (318, "114+51*4"),
273    (325, "-(1-14)*5*(1+4)"),
274    (327, "-(114-5)*(1-4)"),
275    (329, "(11-4)*(51-4)"),
276    (335, "-1+14*(5+1)*4"),
277    (336, "1*14*(5+1)*4"),
278    (337, "1-14*-(5+1)*4"),
279    (341, "11*(45-14)"),
280    (349, "-1+14*5*(1+4)"),
281    (350, "1*(1+4)*5*14"),
282    (351, "1+14*-5*-(1+4)"),
283    (352, "(1+1)*(45-1)*4"),
284    (353, "(11-4)*51-4"),
285    (357, "(114+5)*-(1-4)"),
286    (360, "(1+1)*45*1*4"),
287    (361, "(11-4)*51+4"),
288    (363, "(1+1451)/4"),
289    (368, "(1+1)*(45+1)*4"),
290    (375, "(1+14)*5*(1+4)"),
291    (376, "(1+1)*4*(51-4)"),
292    (385, "(11-4)*(51+4)"),
293    (396, "11*4*-(5-14)"),
294    (400, "-114+514"),
295    (404, "(1+1)*4*51-4"),
296    (412, "(1+1)*4*51+4"),
297    (432, "(1-145)*(1-4)"),
298    (434, "-1-145*(1-4)"),
299    (435, "-1*145*(1-4)"),
300    (436, "-11+451-4"),
301    (438, "(1+145)*-(1-4)"),
302    (440, "(1+1)*4*(51+4)"),
303    (444, "-11+451+4"),
304    (445, "-1-1+451-4"),
305    (446, "1*-1+451-4"),
306    (447, "1/1*451-4"),
307    (448, "1+1*451-4"),
308    (449, "1+1+451-4"),
309    (450, "(1+1)*45*(1+4)"),
310    (452, "114*(5-1)-4"),
311    (453, "-1-1+451+4"),
312    (454, "-1+1*451+4"),
313    (455, "1-1+451+4"),
314    (456, "1*1+451+4"),
315    (457, "1+1+451+4"),
316    (458, "11+451-4"),
317    (460, "114*(5-1)+4"),
318    (466, "11+451+4"),
319    (470, "-11*4+514"),
320    (476, "(114+5)/1*4"),
321    (480, "11*(45-1)-4"),
322    (481, "11*45-14"),
323    (488, "11*(45-1)+4"),
324    (490, "11*45-1-4"),
325    (491, "11*45-1*4"),
326    (492, "11*45+1-4"),
327    (495, "11*(4+5)*(1+4)"),
328    (498, "11*45-1+4"),
329    (499, "11*45*1+4"),
330    (500, "11*45+1+4"),
331    (501, "1-14+514"),
332    (502, "11*(45+1)-4"),
333    (506, "-(1+1)*4+514"),
334    (507, "-11+4+514"),
335    (508, "-1-1-4+514"),
336    (509, "11*45+14"),
337    (510, "1-1-4+514"),
338    (511, "1*1-4+514"),
339    (512, "1+1-4+514"),
340    (513, "-11*(4-51)-4"),
341    (514, "(1-1)/4+514"),
342    (516, "-1-1+4+514"),
343    (517, "-1+1*4+514"),
344    (518, "1-1+4+514"),
345    (519, "1+1*4+514"),
346    (520, "1+1+4+514"),
347    (521, "11-4+514"),
348    (522, "(1+1)*4+514"),
349    (527, "-1+14+514"),
350    (528, "1*14+514"),
351    (529, "1+14+514"),
352    (545, "(114-5)*(1+4)"),
353    (556, "114*5-14"),
354    (558, "11*4+514"),
355    (560, "(1+1)*4*5*14"),
356    (561, "11/4*51*4"),
357    (565, "114*5-1-4"),
358    (566, "114*5*1-4"),
359    (567, "114*5+1-4"),
360    (573, "114*5-1+4"),
361    (574, "114*5/1+4"),
362    (575, "114*5+1+4"),
363    (576, "1*(145-1)*4"),
364    (579, "-1+145*1*4"),
365    (580, "1*145/1*4"),
366    (581, "1+145*1*4"),
367    (584, "114*5+14"),
368    (595, "(114+5)*(1+4)"),
369    (601, "11*(4+51)-4"),
370    (609, "11*(4+51)+4"),
371    (611, "(1-14)*-(51-4)"),
372    (612, "-1*(1-4)*51*4"),
373    (616, "1*-(1-45)*14"),
374    (619, "-11+45*14"),
375    (628, "114+514"),
376    (629, "1*-1+45*14"),
377    (630, "1*1*45*14"),
378    (631, "1*1+45*14"),
379    (632, "1+1+45*14"),
380    (641, "11+45*14"),
381    (644, "1*(1+45)*14"),
382    (649, "11*(45+14)"),
383    (657, "-1+14*(51-4)"),
384    (658, "1*14*(51-4)"),
385    (659, "1+14*(51-4)"),
386    (660, "(114+51)*4"),
387    (667, "-(1-14)*51+4"),
388    (680, "114*(5+1)-4"),
389    (688, "114*(5+1)+4"),
390    (704, "11*4*(5-1)*4"),
391    (705, "(1+14)*(51-4)"),
392    (709, "-1+14*51-4"),
393    (710, "1*14*51-4"),
394    (711, "1+14*51-4"),
395    (715, "(1-14)*-(51+4)"),
396    (717, "-1-14*-51+4"),
397    (718, "1*14*51+4"),
398    (719, "1+14*51+4"),
399    (720, "(1-145)*-(1+4)"),
400    (724, "-1-145*-(1+4)"),
401    (725, "1*145*(1+4)"),
402    (726, "1+145*(1+4)"),
403    (730, "(1+145)*(1+4)"),
404    (761, "(1+14)*51-4"),
405    (769, "(11+4)*51+4"),
406    (770, "1*14*(51+4)"),
407    (771, "1+14*(51+4)"),
408    (784, "(11+45)*14"),
409    (805, "-11+4*51*4"),
410    (814, "-1-1+4*51*4"),
411    (815, "-1+1*4*51*4"),
412    (816, "1*1*4*51*4"),
413    (817, "1*1+4*51*4"),
414    (818, "1+1+4*51*4"),
415    (825, "(11+4)*(51+4)"),
416    (827, "11+4*51*4"),
417    (836, "11*4*(5+14)"),
418    (880, "11*4*5*1*4"),
419    (894, "(1+1)*(451-4)"),
420    (898, "(1+1)*451-4"),
421    (906, "(1+1)*451+4"),
422    (910, "-(1-14)*5*14"),
423    (979, "-1+14*5*14"),
424    (980, "1*14*5*14"),
425    (981, "1+14*5*14"),
426    (1020, "1*(1+4)*51*4"),
427    (1026, "114*-(5-14)"),
428    (1036, "(1+1)*(4+514)"),
429    (1050, "(11+4)*5*14"),
430    (1056, "11*4*(5+1)*4"),
431    (1100, "11*4*5*(1+4)"),
432    (1131, "1145-14"),
433    (1140, "(1145-1)-4"),
434    (1141, "1145-1*4"),
435    (1142, "1145+1-4"),
436    (1148, "1145-1+4"),
437    (1149, "1145+1*4"),
438    (1150, "1145+1+4"),
439    (1159, "1145+14"),
440    (1260, "(1+1)*45*14"),
441    (1386, "11*(4+5)*14"),
442    (1428, "(11-4)*51*4"),
443    (1446, "-1+1451-4"),
444    (1447, "1*1451-4"),
445    (1448, "1+1451-4"),
446    (1454, "-1+1451+4"),
447    (1455, "1*1451+4"),
448    (1456, "1+1451+4"),
449    (1485, "11*-45*(1-4)"),
450    (1526, "(114-5)*14"),
451    (1542, "1*-(1-4)*514"),
452    (1632, "(1+1)*4*51*4"),
453    (1666, "(114+5)*14"),
454    (1710, "114*-5*(1-4)"),
455    (1760, "-(11-451)*4"),
456    (1793, "-11+451*4"),
457    (1800, "1*-(1-451)*4"),
458    (1802, "-1-1+451*4"),
459    (1803, "1*-1+451*4"),
460    (1804, "1-1+451*4"),
461    (1805, "1+1*451*4"),
462    (1806, "1+1+451*4"),
463    (1808, "1*(1+451)*4"),
464    (1815, "11+451*4"),
465    (1824, "114*(5-1)*4"),
466    (1848, "(11+451)*4"),
467    (1936, "11*(45-1)*4"),
468    (1980, "11*45*1*4"),
469    (2016, "-(1-145)*14"),
470    (2024, "11*(45+1)*4"),
471    (2029, "-1+145*14"),
472    (2030, "1*145*14"),
473    (2031, "1+145*14"),
474    (2044, "(1+145)*14"),
475    (2045, "-11+4*514"),
476    (2054, "-1-1+4*514"),
477    (2055, "-1/1+4*514"),
478    (2056, "1/1*4*514"),
479    (2057, "1/1+4*514"),
480    (2058, "1+1+4*514"),
481    (2067, "11+4*514"),
482    (2068, "11*4*(51-4)"),
483    (2166, "114*(5+14)"),
484    (2240, "11*4*51-4"),
485    (2248, "11*4*51+4"),
486    (2280, "114*5*1*4"),
487    (2420, "11*4*(51+4)"),
488    (2475, "11*45*(1+4)"),
489    (2570, "1*(1+4)*514"),
490    (2652, "(1-14)*51*-4"),
491    (2736, "114*(5+1)*4"),
492    (2850, "114*5*(1+4)"),
493    (2855, "-1+14*51*4"),
494    (2856, "1*14*51*4"),
495    (2857, "1+14*51*4"),
496    (3060, "(11+4)*51*4"),
497    (3080, "11*4*5*14"),
498    (3435, "-1145*(1-4)"),
499    (3598, "(11-4)*514"),
500    (3608, "(1+1)*451*4"),
501    (4112, "(1+1)*4*514"),
502    (4503, "-11+4514"),
503    (4512, "-1-1+4514"),
504    (4513, "-1*1+4514"),
505    (4514, "1-1+4514"),
506    (4515, "1+1*4514"),
507    (4516, "1+1+4514"),
508    (4525, "11+4514"),
509    (4576, "(1145-1)*4"),
510    (4580, "1145*1*4"),
511    (4584, "(1145+1)*4"),
512    (4917, "11*(451-4)"),
513    (4957, "11*451-4"),
514    (4965, "11*451+4"),
515    (5005, "11*(451+4)"),
516    (5358, "114*(51-4)"),
517    (5610, "-11*(4-514)"),
518    (5698, "11*(4+514)"),
519    (5725, "1145*(1+4)"),
520    (5800, "(1-1451)*-4"),
521    (5803, "-1+1451*4"),
522    (5804, "1*1451*4"),
523    (5805, "1+1451*4"),
524    (5808, "(1+1451)*4"),
525    (5810, "114*51-4"),
526    (5818, "114*51+4"),
527    (6270, "114*(51+4)"),
528    (6682, "(1-14)*-514"),
529    (6930, "11*45*14"),
530    (7195, "-1+14*514"),
531    (7196, "1*14*514"),
532    (7197, "1+14*514"),
533    (7710, "(1+14)*514"),
534    (7980, "114*5*14"),
535    (8976, "11*4*51*4"),
536    (9028, "(1+1)*4514"),
537    (11447, "11451-4"),
538    (11455, "11451+4"),
539    (14513, "-1+14514"),
540    (14514, "1*14514"),
541    (14515, "1+14514"),
542    (16030, "1145*14"),
543    (19844, "11*451*4"),
544    (22616, "11*4*514"),
545    (23256, "114*51*4"),
546    (45804, "11451*4"),
547    (49654, "11*4514"),
548    (58596, "114*514"),
549    (114514, "114514"),
550    (229028, "(114514+114514)"),
551];
552
553// 大数，1024 bit 的无符号整型
554construct_uint! {
555    struct U1024(16);
556}
557
558enum Infimum {
559    Less(u32),
560    Eqaul,
561}
562
563// 使用二分搜索，凭数字字符串获取 114514 算式
564fn get_by_str(num: &str) -> &'static str {
565    let num: u32 = num.parse().unwrap();
566    let i = MEMO.binary_search_by_key(&num, |&(k, _)| k).unwrap();
567
568    MEMO[i].1
569}
570
571// 使用二分搜索，寻找 x 的最大下界，用于计算除数
572fn infimum_of(x: u32) -> Infimum {
573    // 特判，对于过大的 x 立即返回
574    if x > 229028 {
575        return Infimum::Less(229028);
576    }
577
578    let mut low = 0;
579    let mut high = MEMO.len() - 1; // 避免 mid + 1 == len
580
581    while low < high {
582        let mid = (low + high) / 2;
583        let infimum = MEMO[mid].0; // 可能的最大下确界
584
585        match x.cmp(&infimum) {
586            Ordering::Equal => {
587                return Infimum::Eqaul;
588            }
589
590            Ordering::Greater => {
591                if x < MEMO[mid + 1].0 {
592                    return Infimum::Less(infimum);
593                } else {
594                    low = mid + 1;
595                }
596            }
597
598            Ordering::Less => {
599                high = mid;
600            }
601        }
602    }
603
604    // 二分迭代结束，却仍未退出，
605    // 结合开头，说明是 229028
606    Infimum::Eqaul
607}
608
609// 递归分解大数至不完全 114514 算式
610fn decompose(num: U1024) -> String {
611    let div = match num.try_into() {
612        Ok(x) => match infimum_of(x) {
613            // 取最大下确界
614            Infimum::Less(infimum) => infimum,
615            // 已缓存，则返回相应键作为基本元素，稍后替换
616            Infimum::Eqaul => return x.to_string(),
617        },
618
619        // num 过大，使用最大键作为除数
620        Err(_) => 229028u32,
621    };
622
623    let quotient = decompose(num / div);
624    let remainder = decompose(num % div);
625
626    RE01.replace_all(&format!("{div}*({quotient})+({remainder})"), "")
627        .to_string()
628}
629
630/// Decompose integer into the combination of 114514 formulae.
631///
632/// # Failure
633/// - The integer doesn't meet the condition, --2<sup>1024</sup> + 1 ≤ `num` ≤ 2<sup>1024</sup> -- 1 .
634/// - There are invalid characters in `num`.
635pub fn roar(mut num: &str) -> Result<String, FromDecStrErr> {
636    // 若传入参数为负，则标记，并脱去负号
637    let minus = match num.strip_prefix('-') {
638        Some(positive) => {
639            num = positive;
640            true
641        }
642        None => false,
643    } && num != "0";
644    let x = U1024::from_dec_str(num)?;
645    let mut s = decompose(x);
646
647    // 若执行展开，则改变 s
648    if let Cow::Owned(expansion) = RE_DIGITS.replace_all(&s, |caps: &Captures| {
649        get_by_str(caps.get(0).unwrap().as_str())
650    }) {
651        s = expansion;
652    }
653
654    if minus {
655        s = format!("(11-4-5+1-4)*({s})");
656    }
657
658    while let Cow::Owned(peeled) = RE乘除冗余括号.replace(&s, "$1$2") {
659        s = peeled;
660    }
661
662    while let Cow::Owned(peeled) = RE加减冗余括号.replace(&s, "$1$2$3") {
663        s = peeled;
664    }
665
666    while let Cow::Owned(peeled) = RE行末加减冗余括号.replace(&s, "$1$2") {
667        s = peeled;
668    }
669
670    // 使用 Cow<str> ，避免最后不必要的复制
671    let peeled = RE行冗余括号.replace(&s, "$1");
672
673    Ok(peeled.replace("+-", "-"))
674}
homo/lib.rs

homo/
lib.rs
