trit_core/
ast.rs

1//! 表达式抽象语法树（AST）。
2//!
3//! 语法（优先级从低到高）：
4//!
5//! ```text
6//! expr    := equiv
7//! equiv   := implies ( ("≡" | "==" | "<=>") implies )*
8//! implies := or ( ("=>" | "→") or )*            // 右结合
9//! or      := xor ( ("∨" | "|" | "||") xor )*
10//! xor     := and ( ("⊕" | "^") and )*
11//! and     := unary ( ("∧" | "&" | "&&") unary )*
12//! unary   := ("!" | "~" | "¬") unary | primary
13//! primary := "(" expr ")" | ident | const
14//! const   := "0" | "1" | "X" | "x" | "?" | "True" | "False"
15//! ```
16//!
17//! `¬` 的优先级高于 `∧`，`∧` 高于 `∨`，`∨` 高于 `⊕` 之外的混合用法由
18//! 上表固定；`⊕` 夹在 `∨` 与 `∧` 之间，表示强加法。
19
20use serde::{Deserialize, Serialize};
21
22/// 表达式节点。
23#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
24pub enum Expr {
25    /// 逻辑常量。
26    Const(crate::value::Ternary),
27    /// 变量引用。
28    Var(String),
29    /// 否定 `¬a`。
30    Not(Box<Expr>),
31    /// 与 `a ∧ b`。
32    And(Box<Expr>, Box<Expr>),
33    /// 或 `a ∨ b`。
34    Or(Box<Expr>, Box<Expr>),
35    /// 强加法 `a ⊕ b`。
36    Xor(Box<Expr>, Box<Expr>),
37    /// 蕴含 `a ⇒ b`（右结合）。
38    Implies(Box<Expr>, Box<Expr>),
39    /// 等价 `a ≡ b`。
40    Equiv(Box<Expr>, Box<Expr>),
41}
42
43impl Expr {
44    /// 构造与节点。
45    pub fn and(a: Expr, b: Expr) -> Self {
46        Self::And(Box::new(a), Box::new(b))
47    }
48    /// 构造或节点。
49    pub fn or(a: Expr, b: Expr) -> Self {
50        Self::Or(Box::new(a), Box::new(b))
51    }
52    /// 构造否定节点。
53    ///
54    /// 命名为 `logical_not` 而非 `not`，避免与 `std::ops::Not::not` 混淆。
55    pub fn logical_not(a: Expr) -> Self {
56        Self::Not(Box::new(a))
57    }
58    /// 构造强加法节点。
59    pub fn xor(a: Expr, b: Expr) -> Self {
60        Self::Xor(Box::new(a), Box::new(b))
61    }
62    /// 构造蕴含节点。
63    pub fn implies(a: Expr, b: Expr) -> Self {
64        Self::Implies(Box::new(a), Box::new(b))
65    }
66    /// 构造等价节点。
67    pub fn equiv(a: Expr, b: Expr) -> Self {
68        Self::Equiv(Box::new(a), Box::new(b))
69    }
70
71    /// 是否为常量 `Unknown`。
72    pub const fn is_unknown_const(&self) -> bool {
73        matches!(self, Self::Const(crate::value::Ternary::Unknown))
74    }
75
76    /// 收集表达式中出现的全部变量名（保持首次出现顺序）。
77    pub fn variables(&self) -> Vec<String> {
78        let mut out = Vec::new();
79        let mut seen = std::collections::HashSet::new();
80        self.collect_vars(&mut out, &mut seen);
81        out
82    }
83
84    fn collect_vars(&self, out: &mut Vec<String>, seen: &mut std::collections::HashSet<String>) {
85        match self {
86            Self::Const(_) => {}
87            Self::Var(name) => {
88                if seen.insert(name.clone()) {
89                    out.push(name.clone());
90                }
91            }
92            Self::Not(a) => a.collect_vars(out, seen),
93            Self::And(a, b) | Self::Or(a, b) | Self::Xor(a, b) => {
94                a.collect_vars(out, seen);
95                b.collect_vars(out, seen);
96            }
97            Self::Implies(a, b) | Self::Equiv(a, b) => {
98                a.collect_vars(out, seen);
99                b.collect_vars(out, seen);
100            }
101        }
102    }
103
104    /// 节点总数（用于复杂度统计）。
105    pub fn node_count(&self) -> usize {
106        match self {
107            Self::Const(_) | Self::Var(_) => 1,
108            Self::Not(a) => 1 + a.node_count(),
109            Self::And(a, b)
110            | Self::Or(a, b)
111            | Self::Xor(a, b)
112            | Self::Implies(a, b)
113            | Self::Equiv(a, b) => 1 + a.node_count() + b.node_count(),
114        }
115    }
116
117    /// 树的最大深度。
118    pub fn depth(&self) -> usize {
119        match self {
120            Self::Const(_) | Self::Var(_) => 1,
121            Self::Not(a) => 1 + a.depth(),
122            Self::And(a, b)
123            | Self::Or(a, b)
124            | Self::Xor(a, b)
125            | Self::Implies(a, b)
126            | Self::Equiv(a, b) => 1 + a.depth().max(b.depth()),
127        }
128    }
129
130    /// 渲染为规范的中缀记法（带全角运算符），用于展示与化简输出。
131    pub fn to_infix(&self) -> String {
132        match self {
133            Self::Const(v) => v.to_string(),
134            Self::Var(name) => name.clone(),
135            Self::Not(a) => format!("¬({})", a.to_infix()),
136            Self::And(a, b) => format!("({} ∧ {})", a.to_infix(), b.to_infix()),
137            Self::Or(a, b) => format!("({} ∨ {})", a.to_infix(), b.to_infix()),
138            Self::Xor(a, b) => format!("({} ⊕ {})", a.to_infix(), b.to_infix()),
139            Self::Implies(a, b) => format!("({} ⇒ {})", a.to_infix(), b.to_infix()),
140            Self::Equiv(a, b) => format!("({} ≡ {})", a.to_infix(), b.to_infix()),
141        }
142    }
143}
144
145impl std::fmt::Display for Expr {
146    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
147        f.write_str(&self.to_infix())
148    }
149}
150
151#[cfg(test)]
152mod tests {
153    use super::*;
154    use crate::value::Ternary;
155
156    #[test]
157    fn collects_variables_in_order() {
158        let e = Expr::and(
159            Expr::Var("a".into()),
160            Expr::or(Expr::Var("b".into()), Expr::Var("a".into())),
161        );
162        assert_eq!(e.variables(), vec!["a".to_string(), "b".to_string()]);
163    }
164
165    #[test]
166    fn node_count_and_depth() {
167        let e = Expr::and(Expr::Var("a".into()), Expr::Var("b".into()));
168        assert_eq!(e.node_count(), 3);
169        assert_eq!(e.depth(), 2);
170    }
171
172    #[test]
173    fn infix_rendering() {
174        let e = Expr::logical_not(Expr::Var("a".into()));
175        assert_eq!(e.to_infix(), "¬(a)");
176        let e2 = Expr::equiv(Expr::Const(Ternary::True), Expr::Var("x".into()));
177        assert_eq!(e2.to_infix(), "(1 ≡ x)");
178    }
179}
trit_core/ast.rs

trit_core/
ast.rs
