catalan 0.3.3

binary tree of n variables where the parent node represents a function and the child node represents a value.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

use std::{
    fmt::{Debug, Formatter, Write},
    sync::Arc,
};

use crate::{BinaryNode, ExpressionNode};

#[derive(Default)]
pub struct ReversePolishNotation {
    // true = push
    // false = pop
    stack: Vec<bool>,
}

impl Debug for ReversePolishNotation {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        f.write_char('[')?;
        for (i, s) in self.stack.iter().enumerate() {
            if i != 0 {
                f.write_str(", ")?;
            }
            match s {
                true => f.write_char('+')?,
                false => f.write_char('-')?,
            }
        }
        f.write_char(']')
    }
}

impl ReversePolishNotation {
    pub fn push(&mut self, binary: &BinaryNode) {
        match binary {
            BinaryNode::Atomic => {
                self.stack.push(true);
            }
            BinaryNode::Binary { lhs, rhs } => {
                self.push(rhs);
                self.push(lhs);
                self.stack.push(false);
            }
        }
    }

    pub fn build_expression<V, O>(&self, mut values: Vec<V>, mut operators: Vec<O>) -> Arc<ExpressionNode<V, O>> {
        assert_eq!(values.len(), operators.len() + 1);
        match self.build_stack(&mut values, &mut operators).and_then(|mut e| e.pop()) {
            Some(s) => s,
            None => {
                panic!("Invalid stack state");
            }
        }
    }

    pub fn build_stack<V, O>(&self, values: &mut Vec<V>, operators: &mut Vec<O>) -> Option<Vec<Arc<ExpressionNode<V, O>>>> {
        let mut stack: Vec<Arc<ExpressionNode<V, O>>> = vec![];
        for action in &self.stack {
            match action {
                true => {
                    let value = values.pop()?;
                    stack.push(ExpressionNode::atomic(value));
                }
                false => {
                    let rhs = stack.pop()?;
                    let lhs = stack.pop()?;
                    let operator = operators.pop()?;
                    stack.push(ExpressionNode::binary(operator, &lhs, &rhs));
                }
            }
        }
        Some(stack)
    }
}

impl BinaryNode {
    /// Convert a full binary tree to reverse polish notation
    pub fn as_rpn(&self) -> ReversePolishNotation {
        let mut sequence = ReversePolishNotation::default();
        sequence.push(self);
        sequence
    }
}