Rust 实现一个表达式 Parser(11) Format 实现

本文将完成最终一个需求: 格式化表达式

源码: src/traversal/format.rs

完成目标

将这个表达式 "1*2+(3/(4+(-5)))" 处理成 "1 * 2 + 3 / (4 + (-5))"

也便是说

• 去除冗余括号
• 只保留必要括号
• 在操作符左右刺进空格

写一下

Formatter 界说

像前面的 eval 一样, 这儿直接界说一个结构体来承载逻辑

pub struct Formatter {
    output: String,
}
impl Formatter {
    pub fn new() -> Self {
        Formatter { output: String::new() }
    }
    pub fn format(&mut self, node: &Node) -> &str {
        // 随后就会完成 Visitor Trait
        self.visit(node);
        self.output.as_str()
    }
}

工具函数完成

考虑到格式化会需求刺进一些固定的符号, 如空格, 括号之类的, 因而先来简略完成一些工具函数

impl Formatter {
    fn push(&mut self, str: &str) {
        self.output.push_str(str)
    }
    // 刺进一个空格
    fn ws(&mut self) {
        self.push(" ");
    }
}

Visitor 完成

下面来正式完成格式化逻辑, 比较简略, 直接贴代码

// 不需求返回值, 因而传入 ()
impl Visitor<()> for Formatter {
    // Literal 直接刺进
    fn visit_num(&mut self, _: i32, raw: &str) {
        self.push(raw)
    }
    fn visit_expr(&mut self, left: &Node, op: &str, right: &Node) {
        // 优先拜访左子树
        self.visit(left);
        // 刺进空格
        self.ws();
        // 刺进操作符
        self.push(op);
        // 刺进空格
        self.ws();
        // 拜访右子树
        self.visit(right);
    }
}

处理括号

这儿简略的分析一下, 何时需求增加括号

榜首反应想到的便是操作数是一个负数 "1 + (-2)", 这种状况下括号不行省略, 但是假如榜首个操作数是负数呢 "-1 + 2", 这种状况下括号可省略, 综合一下, 咱们的榜首种状况得到了

• 右子树是一个负数

第二种状况就需求思考一下括号的语义了, 在数学四则运算中, 括号表明进步表达式的核算优先级, 意为优先核算, 而咱们在 Parser 阶段本就会根据核算优先级来构建 AST, 也便是说在 AST 中本来就已经隐含了核算优先级的问题, 也便是 节点所处深度越大, 优先级越高

但是假如碰到如下图中的 AST 呢

很显然, 这不符合常理, 由于加法的优先级就应该比乘法要低, 但是这儿为什么加法节点的深度要比乘法节点的深度大呢

由于这儿 AST(Abstract Syntax Tree) abstract 掉了一对括号, 这棵 AST 的表达式应该是 "1 * (2 + 3)"

发现了这点就很容易得出第二个状况了, 在这种状况下咱们必须增加括号

• 右子树的符号的优先级小于当时符号的优先级

以下是代码的具体完成

impl Formatter {
    // 将给定表达式包裹在括号中
    fn push_paren_expr(&mut self, node: &Node) {
      // 先增加括号
      self.push("(");
      // 在拜访节点
      self.visit(node);
      self.push(")");
    }
}
impl Visitor<()> for Formatter {
    // 数字依然直接刺进
    fn visit_num(&mut self, _: i32, raw: &str) {
        self.push(raw)
    }
    fn visit_expr(&mut self, left: &Node, op: &str, right: &Node) {
        // 左子树依然直接拜访
        self.visit(left);
        self.ws();
        // 符号依然直接刺进
        self.push(op);
        self.ws();
        // 拜访右子树前先做个判别
        match right {
            // 若当时符号的优先级大于右子树符号的优先级
            Node::Expr { op: next_op, .. }
                if SyntaxKind::get_op_priority(op)
                    > SyntaxKind::get_op_priority(next_op.into_str()) =>
            {
                // 把右子树裹在括号里
                self.push_paren_expr(right);
            }
            // 若右子树是个负数
            Node::Literal { raw, .. } if raw.chars().nth(0) == Some('-') => {
                // 把右子树裹在括号里
                self.push_paren_expr(right);
            }
            // 其他状况不需求特殊处理
            _ => {
                self.visit(right);
            }
        }
    }
}

跑一下

确实是没有问题

#[test]
fn smoke_test() {
    let mut f = Formatter::new();
    assert_eq!(
        "1 * 2 + 3 / (4 + (-5))",
        f.format(&get_node("1*2+(3/(4+(-5)))"))
    )
}

模块导出

源码: src/traversal/mod.rs

如下

pub fn eval(root: &Node) -> i32 {
    Executor::new().eval(root)
}
pub fn format(root: &Node) -> String {
    Formatter::new().format(root).to_string()
}