Solution to "H. Higher Order Functions": https://codeforces.com/contest/1578/problem/H

higher_order_functions.rs

/// https://codeforces.com/contest/1578/problem/H

use std::{str::FromStr, cmp::max, vec};

#[derive(Debug, Clone, PartialEq, Eq)]
enum AST {
    Unit,
    Paren(Box<AST>),
    Func(Box<AST>, Box<AST>),
}

#[derive(Debug, PartialEq, Eq)]
struct ASTParseError(String);

type Result<T> = std::result::Result<T, ASTParseError>;

impl AST {
    fn tokenize(s: &str) -> Result<Vec<String>> {
        let mut tokens: Vec<String> = vec![];
        let mut previous_char: char = Default::default();

        for char in s.chars() {
            match char {
                '(' => {
                    if previous_char == '(' {
                        tokens.push(previous_char.into())
                    }
                }
                ')' => {
                    if previous_char == '(' {
                        // Unit
                        tokens.push("()".into())
                    } else {
                        tokens.push(char.into());
                    }
                }
                '-' => (),
                '>' => {
                    if previous_char == '-' {
                        tokens.push("->".into())
                    } else {
                        return Err(ASTParseError(format!(
                            "Unexpected previous character {:?}.",
                            previous_char
                        )));
                    }
                }
                _ => return Err(ASTParseError(format!("Unexpected character {:?}.", char))),
            }
            previous_char = char
        }

        Ok(tokens)
    }

    fn new(tokens: Vec<String>) -> Result<Self> {
        let length = tokens.len();

        if length == 0 {
            return Err(ASTParseError("Unexpected end of token sequence.".into()));
        }

        let first = &tokens[0];

        match first.as_str() {
            "()" => {
                if length == 1 {
                    Ok(Self::Unit)
                } else {
                    if tokens[1] == "->" {
                        Ok(Self::Func(
							Box::new(Self::Unit),
							Box::new(Self::new(tokens[2..].to_vec())?),
						))
                    } else {
                        Err(ASTParseError(format!("Unexpected token {:?}.", tokens[1])))
                    }
                }
            }
            "(" => {
				if let Some((closing_paren_index, _)) = tokens.iter().enumerate().filter(|(_, token)| *token == ")").nth_back(0) {
					let node = Self::Paren(Box::new(Self::new(
                        tokens[1..closing_paren_index].to_vec(),
                    )?));

					if closing_paren_index + 1 < length {
						if tokens[closing_paren_index + 1] == "->" {
							Ok(Self::Func(
								Box::new(node),
								Box::new(Self::new(tokens[closing_paren_index + 2..].to_vec())?),
							))
						} else {
							Err(ASTParseError(format!("Unexpected token {:?}.", tokens[closing_paren_index + 1])))
						}
                    } else {
						Ok(node)
                    } 
				} else {
					Err(ASTParseError(format!("Unclosed parentheses: {:?}.", tokens)))
				}
            }
            _ => return Err(ASTParseError(format!("Unexpected token {:?}.", first))),
        }
    }

	fn order(self) -> usize {
		match self {
			Self::Unit => 0,
			Self::Paren(node) => node.order(),
			Self::Func(left, right) => max(left.order() + 1, right.order())
		}
	}
}

impl FromStr for AST {
    type Err = ASTParseError;

    fn from_str(s: &str) -> Result<Self> {
        Self::new(AST::tokenize(s)?)
    }
}

fn main() {
    for (definition, order) in vec![
		("()", 0),
		("()->()", 1),
		("()->()->()", 1),
		("(()->())->()", 2),
		("()->(((()->())->()->())->())", 3),
	] {
		let tree = AST::from_str(definition).expect("Defintion to parse");
		assert_eq!(tree.order(), order);
	}
}