字符串解析的生产级实现：从 atoi 到状态机

Paul 收录于 Go

2022-04-14 约 2144 字预计阅读 5 分钟

LeetCode 的 atoi 是经典面试题，但生产级的实现远比面试版本复杂。这篇文章从面试版本出发，逐步分析 Go 和 Rust 标准库的实现，理解"生产级"代码的设计思想。

一、面试版 atoi

1.1 LeetCode 8: String to Integer

基本要求：

跳过前导空格
识别正负号
转换数字字符
处理溢出

func myAtoi(s string) int {
    i, n := 0, len(s)
    
    // 跳过空格
    for i < n && s[i] == ' ' {
        i++
    }
    
    if i >= n {
        return 0
    }
    
    // 处理符号
    sign := 1
    if s[i] == '+' {
        i++
    } else if s[i] == '-' {
        sign = -1
        i++
    }
    
    // 转换数字
    result := 0
    for i < n && s[i] >= '0' && s[i] <= '9' {
        digit := int(s[i] - '0')
        
        // 溢出检查
        if result > (math.MaxInt32-digit)/10 {
            if sign == 1 {
                return math.MaxInt32
            }
            return math.MinInt32
        }
        
        result = result*10 + digit
        i++
    }
    
    return sign * result
}

这个版本能通过 LeetCode，但离生产级还差很远。

1.2 缺少什么？

面试版本	生产级需求
只处理 int32	支持多种类型 (int8, int64, uint…)
只返回结果	需要返回详细错误
只支持十进制	支持多进制 (2, 8, 16…)
简单溢出处理	精确的溢出检测
固定格式	支持 0x, 0o, 0b 前缀

二、Go 标准库分析

2.1 strconv.ParseInt 签名

func ParseInt(s string, base int, bitSize int) (i int64, err error)

// 参数：
//   s: 输入字符串
//   base: 进制 (0 表示自动检测)
//   bitSize: 目标类型位数 (8, 16, 32, 64)

// 返回：
//   i: 解析结果
//   err: 错误信息 (包含详细原因)

2.2 错误类型

type NumError struct {
    Func string // 函数名 ("ParseInt")
    Num  string // 输入字符串
    Err  error  // 具体错误
}

var (
    ErrRange = errors.New("value out of range")
    ErrSyntax = errors.New("invalid syntax")
)

2.3 源码分析

// src/strconv/atoi.go (简化版)
func ParseInt(s string, base int, bitSize int) (i int64, err error) {
    // 空字符串
    if s == "" {
        return 0, syntaxError("ParseInt", s)
    }
    
    // 处理符号
    s0 := s
    neg := false
    if s[0] == '+' {
        s = s[1:]
    } else if s[0] == '-' {
        neg = true
        s = s[1:]
    }
    
    // 处理进制前缀
    if base == 0 {
        base = 10
        if s[0] == '0' {
            switch {
            case len(s) >= 2 && lower(s[1]) == 'x':
                base = 16
                s = s[2:]
            case len(s) >= 2 && lower(s[1]) == 'o':
                base = 8
                s = s[2:]
            case len(s) >= 2 && lower(s[1]) == 'b':
                base = 2
                s = s[2:]
            default:
                base = 8
                s = s[1:]
            }
        }
    }
    
    // 计算溢出边界
    var cutoff uint64
    switch bitSize {
    case 8:
        cutoff = uint64(1<<7 - 1)
    case 16:
        cutoff = uint64(1<<15 - 1)
    case 32:
        cutoff = uint64(1<<31 - 1)
    case 64:
        cutoff = uint64(1<<63 - 1)
    }
    if neg {
        cutoff++
    }
    
    // 逐字符转换
    var n uint64
    for _, c := range []byte(s) {
        var d byte
        switch {
        case '0' <= c && c <= '9':
            d = c - '0'
        case 'a' <= lower(c) && lower(c) <= 'z':
            d = lower(c) - 'a' + 10
        default:
            return 0, syntaxError("ParseInt", s0)
        }
        
        if d >= byte(base) {
            return 0, syntaxError("ParseInt", s0)
        }
        
        // 溢出检查（在乘法之前）
        if n >= cutoff {
            return 0, rangeError("ParseInt", s0)
        }
        
        n *= uint64(base)
        n1 := n + uint64(d)
        
        // 检查加法溢出
        if n1 < n || n1 > cutoff {
            return 0, rangeError("ParseInt", s0)
        }
        n = n1
    }
    
    if neg {
        return -int64(n), nil
    }
    return int64(n), nil
}

2.4 设计亮点

溢出检测在运算前：避免先溢出再判断
详细的错误信息：包含原始输入，方便调试
统一处理有符号/无符号：用 uint64 计算，最后转换
自动进制检测：0x, 0o, 0b 前缀

三、状态机实现

3.1 为什么用状态机？

复杂的解析需求很难用 if-else 处理清楚：

有效输入示例：
"  -42"      → -42
"0x1A"       → 26 (自动检测 16 进制)
"   +0o17"   → 15 (自动检测 8 进制)

无效输入示例：
"--42"       → 语法错误
"0x"         → 语法错误（无数字）
"123abc"     → ？（Go 报错，某些语言接受 123）

3.2 状态机模型

         ┌─────────────────────────────────────────────────────┐
         │                                                      │
    ┌────▼────┐  空格   ┌─────────┐  +/-   ┌─────────┐         │
    │  START  │────────▶│ SPACES  │───────▶│  SIGN   │         │
    └─────────┘         └────┬────┘        └────┬────┘         │
         │                   │                   │              │
         │ 0                 │ 数字              │ 数字         │
         ▼                   │                   │              │
    ┌─────────┐              │                   │              │
    │ PREFIX  │◄─────────────┴───────────────────┘              │
    └────┬────┘                                                 │
         │ x/o/b/数字                                           │
         ▼                                                      │
    ┌─────────┐  数字                                           │
    │ DIGITS  │────────┐                                        │
    └────┬────┘        │                                        │
         │             │                                        │
         │ 非数字      │                                        │
         ▼             ▼                                        │
    ┌─────────┐   ┌─────────┐                                   │
    │  ERROR  │   │   END   │───────────────────────────────────┘
    └─────────┘   └─────────┘

3.3 Go 实现

type State int

const (
    StateStart State = iota
    StateSign
    StatePrefix
    StateDigits
    StateEnd
    StateError
)

type Parser struct {
    state   State
    sign    int
    base    int
    result  uint64
    bitSize int
    cutoff  uint64
}

func NewParser(bitSize int) *Parser {
    cutoff := uint64(1<<(bitSize-1) - 1)
    return &Parser{
        state:   StateStart,
        sign:    1,
        base:    10,
        bitSize: bitSize,
        cutoff:  cutoff,
    }
}

func (p *Parser) Feed(c byte) error {
    switch p.state {
    case StateStart:
        return p.handleStart(c)
    case StateSign:
        return p.handleSign(c)
    case StatePrefix:
        return p.handlePrefix(c)
    case StateDigits:
        return p.handleDigits(c)
    default:
        return errors.New("invalid state")
    }
}

func (p *Parser) handleStart(c byte) error {
    switch {
    case c == ' ' || c == '\t':
        // 保持 Start 状态
        return nil
    case c == '+':
        p.state = StateSign
        return nil
    case c == '-':
        p.sign = -1
        p.cutoff++ // 负数可以多一
        p.state = StateSign
        return nil
    case c == '0':
        p.state = StatePrefix
        return nil
    case c >= '1' && c <= '9':
        p.state = StateDigits
        return p.addDigit(c - '0')
    default:
        p.state = StateError
        return errors.New("invalid character")
    }
}

func (p *Parser) handlePrefix(c byte) error {
    switch lower(c) {
    case 'x':
        p.base = 16
        p.state = StateDigits
        return nil
    case 'o':
        p.base = 8
        p.state = StateDigits
        return nil
    case 'b':
        p.base = 2
        p.state = StateDigits
        return nil
    default:
        p.base = 8
        p.state = StateDigits
        return p.addDigit(c - '0')
    }
}

func (p *Parser) addDigit(d byte) error {
    if p.result > p.cutoff/uint64(p.base) {
        return errors.New("overflow")
    }
    p.result = p.result*uint64(p.base) + uint64(d)
    if p.result > p.cutoff {
        return errors.New("overflow")
    }
    return nil
}

func (p *Parser) Result() (int64, error) {
    if p.state == StateError {
        return 0, errors.New("parse error")
    }
    if p.sign < 0 {
        return -int64(p.result), nil
    }
    return int64(p.result), nil
}

四、Rust 标准库对比

4.1 Rust 的 from_str

// Rust 使用 trait 实现
impl FromStr for i32 {
    type Err = ParseIntError;
    
    fn from_str(s: &str) -> Result<i32, ParseIntError> {
        i32::from_str_radix(s, 10)
    }
}

// 使用
let n: i32 = "42".parse()?;
let n = i32::from_str_radix("0x2A", 16)?;

4.2 Rust 的错误处理

pub enum IntErrorKind {
    Empty,           // 空字符串
    InvalidDigit,    // 非法字符
    PosOverflow,     // 正溢出
    NegOverflow,     // 负溢出
    Zero,            // 意外的零（某些场景）
}

4.3 对比

特性	Go	Rust
返回类型	(int64, error)	Result<T, ParseIntError>
进制	参数指定	方法名区分
错误粒度	Error interface	枚举类型
符号处理	内部处理	类型系统区分

五、实战应用

5.1 配置文件解析

type Config struct {
    Port     int
    Timeout  time.Duration
    MaxSize  int64
}

func parseSize(s string) (int64, error) {
    s = strings.TrimSpace(s)
    if len(s) == 0 {
        return 0, nil
    }
    
    // 支持 K, M, G 后缀
    unit := int64(1)
    switch s[len(s)-1] {
    case 'K', 'k':
        unit = 1024
        s = s[:len(s)-1]
    case 'M', 'm':
        unit = 1024 * 1024
        s = s[:len(s)-1]
    case 'G', 'g':
        unit = 1024 * 1024 * 1024
        s = s[:len(s)-1]
    }
    
    n, err := strconv.ParseInt(s, 0, 64)
    if err != nil {
        return 0, err
    }
    
    // 检查乘法溢出
    if n > 0 && unit > math.MaxInt64/n {
        return 0, errors.New("size overflow")
    }
    
    return n * unit, nil
}

// 使用
parseSize("512M")  // 536870912
parseSize("0x100") // 256

5.2 命令行参数

func parsePort(s string) (int, error) {
    port, err := strconv.ParseInt(s, 10, 16)  // 16 位足够端口号
    if err != nil {
        return 0, fmt.Errorf("invalid port: %w", err)
    }
    if port < 1 || port > 65535 {
        return 0, fmt.Errorf("port must be 1-65535, got %d", port)
    }
    return int(port), nil
}

六、总结

层次	实现方式
面试版	if-else，只处理基本情况
生产级	状态机，完整的错误处理
标准库	高度优化，支持多类型多进制

核心收获：

溢出检测要在运算前，不是运算后
状态机让复杂解析逻辑更清晰
错误信息要详细，包含原始输入
边界条件是区分面试代码和生产代码的关键

目录

字符串解析的生产级实现：从 atoi 到状态机

一、面试版 atoi

1.1 LeetCode 8: String to Integer

1.2 缺少什么？

二、Go 标准库分析

2.1 strconv.ParseInt 签名

2.2 错误类型

2.3 源码分析

2.4 设计亮点

三、状态机实现

3.1 为什么用状态机？

3.2 状态机模型

3.3 Go 实现

四、Rust 标准库对比

4.1 Rust 的 from_str

4.2 Rust 的错误处理

4.3 对比

五、实战应用

5.1 配置文件解析

5.2 命令行参数

六、总结