leetcode/
valid_number.rs

1//! # 65. 有效数字
2//!
3//! 难度 困难
4//!
5//! 验证给定的字符串是否可以解释为十进制数字。
6//!
7//! 例如:
8//!
9//! - `"0"` => `true`
10//! - `" 0.1 "` => `true`
11//! - `"abc"` => `false`
12//! - `"1 a"` => `false`
13//! - `"2e10"` => `true`
14//! - `" -90e3   "` => `true`
15//! - `" 1e"` => `false`
16//! - `"e3"` => `false`
17//! - `" 6e-1"` => `true`
18//! - `" 99e2.5 "` => `false`
19//! - `"53.5e93"` => `true`
20//! - `" --6 "` => `false`
21//! - `"-+3"` => `false`
22//! - `"95a54e53"` => `false`
23//!
24//! 说明: 我们有意将问题陈述地比较模糊。在实现代码之前，你应当事先思考所有可能的情况。这里给出一份可能存在于有效十进制数字中的字符列表：
25//!
26//! - 数字 0-9
27//! - 指数 - "e"
28//! - 正/负号 - "+"/"-"
29//! - 小数点 - "."
30//!
31//! 当然，在输入中，这些字符的上下文也很重要。
32//!
33//! See [leetcode](https://leetcode-cn.com/problems/valid-number/)
34
35/// DFA
36///
37/// `enum` + Pattern Matching 实现状态机，再加上 `Iterator`/`Result` 的高阶函数组合工具，
38/// 代码可读性比写个表找下标不知道高哪里去了。
39///
40/// 另外，开始不需要 `trim()`，一是因为这个操作结合起来整个实现并没有这里的实现高效，
41/// 二是内部调用了 `char:is_whitespace()` 不止判断了空格，还有其它空白字符，不一定符合题目的测试用例。
42pub struct Solution;
43
44impl Solution {
45    pub fn is_number(s: String) -> bool {
46        s.chars()
47         .try_fold(State::new(), State::handle)
48         .as_ref()
49         .map_or(false, State::is_valid)
50    }
51}
52
53type Result = std::result::Result<State, ()>;
54
55enum State {
56    Start,
57    Sign,
58    Integer,
59    Dot,
60    EmptyDot,
61    Decimal,
62    E,
63    ExpSign,
64    Exponent,
65    End,
66}
67
68impl State {
69    fn new() -> Self {
70        State::Start
71    }
72
73    fn is_valid(&self) -> bool {
74        use State::*;
75        match self {
76            Start | Sign | E | ExpSign | EmptyDot => false,
77            _ => true,
78        }
79    }
80
81    fn handle(self, c: char) -> Result {
82        use State::*;
83        match self {
84            Start => match c {
85                ' ' => Ok(Start),
86                '+' | '-' => Ok(Sign),
87                '0'..='9' => Ok(Integer),
88                '.' => Ok(EmptyDot),
89                _ => Err(()),
90            }
91            Sign => match c {
92                '0'..='9' => Ok(Integer),
93                '.' => Ok(EmptyDot),
94                _ => Err(()),
95            }
96            Integer => match c {
97                '0'..='9' => Ok(Integer),
98                '.' => Ok(Dot),
99                'e' => Ok(E),
100                ' ' => Ok(End),
101                _ => Err(()),
102            }
103            EmptyDot => match c {
104                '0'..='9' => Ok(Decimal), // "  .1" or "  +.1"
105                _ => Err(()),
106            }
107            Dot => match c {
108                '0'..='9' => Ok(Decimal),
109                'e' => Ok(E),   // "46.e3"
110                ' ' => Ok(End),
111                _ => Err(()),
112            }
113            Decimal => match c {
114                '0'..='9' => Ok(Decimal),
115                'e' => Ok(E),
116                ' ' => Ok(End),
117                _ => Err(()),
118            }
119            E => match c {
120                '+' | '-' => Ok(ExpSign),
121                '0'..='9' => Ok(Exponent),
122                _ => Err(()),
123            }
124            ExpSign => match c {
125                '0'..='9' => Ok(Exponent),
126                _ => Err(()),
127            }
128            Exponent => match c {
129                '0'..='9' => Ok(Exponent),
130                ' ' => Ok(End),
131                _ => Err(()),
132            }
133            End => match c {
134                ' ' => Ok(End),
135                _ => Err(()),
136            }
137        }
138    }
139}
140
141#[cfg(test)]
142mod tests {
143    use super::*;
144    use std::str::FromStr;
145
146    #[test]
147    fn test() {
148        let cases = (
149            // false
150            vec![
151                "+.",
152                ".",
153                "1.0e4.5",
154                "-000111.xxaslkdfjaskldfj",
155                "12 3",
156                "1a3",
157                "",
158                "     ",
159                "46.e",
160                "1e",
161                "+",
162                "-",
163                "+.",
164                "-.",
165            ],
166            // true
167            vec![
168                "123",
169                " 123 ",
170                "0",
171                "0123",  //Cannot agree
172                "00",  //Cannot agree
173                "-10",
174                "-0",
175                "123.5",
176                "123.000000",
177                "-500.777",
178                "0.0000001",
179                "0.00000",
180                "0.",  //Cannot be more disagree!!!
181                "00.5",  //Strongly cannot agree
182                "123e1",
183                "1.23e10",
184                "0.5e-10",
185                "0.5e04",
186                ".1", //Ok, if you say so
187                "2e0",  //Really?!
188                "+.8",
189                " 005047e+6",  //Damn = =|||
190                "-123.456e-789",
191                "46.e3",
192            ]);
193
194        let cases = cases.0.iter().map(|s| (false, s)).chain(cases.1.iter().map(|s| (true, s)));
195        for (expect, &s) in cases {
196            assert_eq!(expect, Solution::is_number(s.into()),
197                "expect is_number(\"{}\") = {}, but got {}, try parse: {:?}", s, expect, !expect, f32::from_str(s.trim()));
198        }
199    }
200}
leetcode/valid_number.rs

leetcode/
valid_number.rs
