Rust 练习册：构建逆波兰表达式计算器

献计献策

887人浏览 · 2025-11-06 17:08:57

献计献策 · 2025-11-06 17:08:57 发布

在计算机科学中，表达式求值是一个经典问题。今天我们将通过实现一个逆波兰表达式（Reverse Polish Notation，RPN）计算器来深入学习 Rust 的枚举类型、模式匹配和栈数据结构的使用。

什么是逆波兰表达式？

逆波兰表达式是一种后缀表达式，操作符位于操作数之后。例如，我们熟悉的中缀表达式 “3 + 4” 在逆波兰表示法中写作 “3 4 +”。这种表示法的优势在于：

不需要括号来指定运算优先级
可以通过简单的栈操作进行求值

让我们通过一些例子来理解：

中缀：“2 + 3” → 后缀：“2 3 +”
中缀：“(4 + 8) / (7 - 5)” → 后缀：“4 8 + 7 5 - /”

核心数据结构

#[derive(Debug)]
pub enum CalculatorInput {
    Add,
    Subtract,
    Multiply,
    Divide,
    Value(i32),
}

我们使用 Rust 的枚举类型来表示计算器的输入。枚举让我们可以清晰地表达有限的几种可能性，这比使用整数常量或字符串要安全得多。

完整实现

#[derive(Debug)]
pub enum CalculatorInput {
    Add,
    Subtract,
    Multiply,
    Divide,
    Value(i32),
}

pub fn evaluate(inputs: &[CalculatorInput]) -> Option<i32> {
    let mut stack: Vec<i32> = Vec::new();
    
    for input in inputs {
        match input {
            CalculatorInput::Value(value) => stack.push(*value),
            _ => {
                if stack.len() < 2 {
                    return None;
                }
                
                let right = stack.pop().unwrap();
                let left = stack.pop().unwrap();
                
                let result = match input {
                    CalculatorInput::Add => left + right,
                    CalculatorInput::Subtract => left - right,
                    CalculatorInput::Multiply => left * right,
                    CalculatorInput::Divide => left / right,
                    CalculatorInput::Value(_) => unreachable!(),
                };
                
                stack.push(result);
            }
        }
    }
    
    if stack.len() == 1 {
        Some(stack[0])
    } else {
        None
    }
}

代码深度解析

枚举与模式匹配

#[derive(Debug)]
pub enum CalculatorInput {
    Add,
    Subtract,
    Multiply,
    Divide,
    Value(i32),
}

枚举是 Rust 中表示多种可能值的强大工具。每个变体可以携带不同类型的数据，如 [Value(i32)](file:///Users/zacksleo/projects/github/zacksleo/exercism-rust/exercises/concept/rpn-calculator/src/lib.rs#L7-L7) 携带一个整数值。

栈操作

let mut stack: Vec<i32> = Vec::new();

for input in inputs {
    match input {
        CalculatorInput::Value(value) => stack.push(*value),
        // ...
    }
}

我们使用 Vec<i32> 作为栈来存储操作数。当遇到数值时，将其压入栈中。

嵌套模式匹配

match input {
    CalculatorInput::Value(value) => stack.push(*value),
    _ => {
        // ...
        let result = match input {
            CalculatorInput::Add => left + right,
            CalculatorInput::Subtract => left - right,
            CalculatorInput::Multiply => left * right,
            CalculatorInput::Divide => left / right,
            CalculatorInput::Value(_) => unreachable!(),
        };
        // ...
    }
}

我们使用了两层模式匹配：

第一层区分是数值还是操作符
第二层确定具体的操作符类型

错误处理

if stack.len() < 2 {
    return None;
}

在执行操作前，我们检查栈中是否有足够的操作数。如果没有，立即返回 None 表示计算失败。

unreachable! 宏

CalculatorInput::Value(_) => unreachable!(),

由于外层已经处理了 [Value](file:///Users/zacksleo/projects/github/zacksleo/exercism-rust/exercises/concept/rpn-calculator/src/lib.rs#L7-L7) 情况，内层的 [Value](file:///Users/zacksleo/projects/github/zacksleo/exercism-rust/exercises/concept/rpn-calculator/src/lib.rs#L7-L7) 分支永远不会被执行。使用 [unreachable!()](file:///Users/zacksleo/projects/github/zacksleo/exercism-rust/exercises/concept/short-fibonacci/src/lib.rs#L13-L13) 宏可以明确表达这一点。

测试用例详解

use rpn_calculator::*;

fn calculator_input(s: &str) -> Vec<CalculatorInput> {
    s.split_whitespace()
        .map(|s| match s {
            "+" => CalculatorInput::Add,
            "-" => CalculatorInput::Subtract,
            "*" => CalculatorInput::Multiply,
            "/" => CalculatorInput::Divide,
            n => CalculatorInput::Value(n.parse().unwrap()),
        })
        .collect()
}

#[test]
fn test_empty_input_returns_none() {
    let input = calculator_input("");
    assert_eq!(evaluate(&input), None);
}

#[test]
fn test_simple_value() {
    let input = calculator_input("10");
    assert_eq!(evaluate(&input), Some(10));
}

#[test]
fn test_simple_addition() {
    let input = calculator_input("2 2 +");
    assert_eq!(evaluate(&input), Some(4));
}

#[test]
fn test_simple_subtraction() {
    let input = calculator_input("7 11 -");
    assert_eq!(evaluate(&input), Some(-4));
}

#[test]
fn test_simple_multiplication() {
    let input = calculator_input("6 9 *");
    assert_eq!(evaluate(&input), Some(54));
}

#[test]
fn test_simple_division() {
    let input = calculator_input("57 19 /");
    assert_eq!(evaluate(&input), Some(3));
}

#[test]
fn test_complex_operation() {
    let input = calculator_input("4 8 + 7 5 - /");
    assert_eq!(evaluate(&input), Some(6));
}

#[test]
fn test_too_few_operands_returns_none() {
    let input = calculator_input("2 +");
    assert_eq!(evaluate(&input), None);
}

#[test]
fn test_too_many_operands_returns_none() {
    let input = calculator_input("2 2");
    assert_eq!(evaluate(&input), None);
}

这些测试用例覆盖了各种情况：

空输入
简单数值
各种基本运算
复杂表达式
错误情况处理

Rust 特性的体现

1. 强大的枚举类型

pub enum CalculatorInput {
    Add,
    Subtract,
    Multiply,
    Divide,
    Value(i32),
}

Rust 的枚举比其他语言中的枚举更加强大，可以携带数据，这使得它们成为表达复杂数据结构的理想选择。

2. 模式匹配的安全性

match input {
    CalculatorInput::Value(value) => stack.push(*value),
    _ => { /* 处理操作符 */ }
}

编译器会确保我们处理了所有可能的枚举变体，避免了运行时错误。

3. Vec 作为栈的使用

let mut stack: Vec<i32> = Vec::new();
stack.push(value);          // 入栈
let value = stack.pop();    // 出栈

标准库中的 Vec 提供了完美的栈操作支持。

4. Option 类型的错误处理

pub fn evaluate(inputs: &[CalculatorInput]) -> Option<i32>

使用 Option 类型明确表示函数可能失败，调用者必须显式处理这种情况。

算法工作原理

RPN 计算器的工作原理如下：

从左到右遍历输入
遇到数值时，压入栈中
遇到操作符时：
- 从栈中弹出两个操作数（注意顺序）
- 执行运算
- 将结果压回栈中
最终栈中应该只剩一个值，即结果

例如，计算 “4 8 + 7 5 - /”：

4 入栈：[4]
8 入栈：[4, 8]
- 运算：4+8=12，12 入栈：[12]
7 入栈：[12, 7]
5 入栈：[12, 7, 5]
- 运算：7-5=2，2 入栈：[12, 2]
/ 运算：12/2=6，6 入栈：[6]
结果：6

实际应用场景

RPN 计算器在许多领域都有应用：

编程语言解释器：许多语言的虚拟机使用栈来执行指令
计算器应用：HP 计算器就以 RPN 著称
表达式求值：编译器将中缀表达式转换为后缀表达式进行求值
图形计算器：PostScript 语言使用 RPN
嵌入式系统：Forth 语言完全基于栈和 RPN

扩展思考

这个实现可以进一步扩展：

impl CalculatorInput {
    pub fn is_operator(&self) -> bool {
        match self {
            CalculatorInput::Value(_) => false,
            _ => true,
        }
    }
}

pub fn evaluate_with_error(inputs: &[CalculatorInput]) -> Result<i32, String> {
    // 返回详细的错误信息
}