326 lines
9.4 KiB
Rust
326 lines
9.4 KiB
Rust
use std::str::FromStr;
|
|
use std::io::BufRead;
|
|
|
|
|
|
#[derive(Debug, PartialEq)]
|
|
enum Operator {
|
|
Add,
|
|
Mul,
|
|
}
|
|
|
|
|
|
#[derive(Debug, PartialEq)]
|
|
struct Node {
|
|
left: Box<Expression>,
|
|
right: Box<Expression>,
|
|
op: Operator,
|
|
}
|
|
|
|
#[derive(Debug, PartialEq)]
|
|
enum ExpressionValue {
|
|
Node(Node),
|
|
Litteral(u64),
|
|
}
|
|
|
|
#[derive(Debug, PartialEq)]
|
|
struct Expression {
|
|
level: usize,
|
|
value: ExpressionValue,
|
|
}
|
|
|
|
#[derive(Debug, PartialEq)]
|
|
enum Token {
|
|
Litteral(u64),
|
|
Add,
|
|
Mul,
|
|
OpeningParenthese,
|
|
ClosingParenthese,
|
|
}
|
|
|
|
#[derive(Debug)]
|
|
struct TokenStream<'a> {
|
|
input: &'a str,
|
|
}
|
|
|
|
impl<'a> TokenStream<'a> {
|
|
fn new(input: &'a str) -> TokenStream {
|
|
TokenStream {
|
|
input
|
|
}
|
|
}
|
|
}
|
|
|
|
impl<'a> Iterator for TokenStream<'a> {
|
|
type Item = Token;
|
|
|
|
fn next(&mut self) -> Option<Self::Item> {
|
|
let mut it = self.input.chars();
|
|
let (token, read) = match it.next() {
|
|
Some('+') => (Some(Token::Add), 1),
|
|
Some('*') => (Some(Token::Mul), 1),
|
|
Some(')') => (Some(Token::ClosingParenthese), 1),
|
|
Some('(') => (Some(Token::OpeningParenthese), 1),
|
|
Some(ch) if ch.is_ascii_digit() => {
|
|
let mut buffer = ch.to_string();
|
|
buffer.push_str(&it.take_while(|ch| ch.is_ascii_digit()).collect::<String>());
|
|
|
|
(Some(Token::Litteral(buffer.parse().unwrap())), buffer.len())
|
|
},
|
|
None => (None, 0),
|
|
_ => unimplemented!()
|
|
};
|
|
|
|
if let None = token {
|
|
None
|
|
} else {
|
|
self.input = &self.input[read..];
|
|
token
|
|
}
|
|
}
|
|
}
|
|
|
|
#[derive(Debug)]
|
|
struct Parser<'a> {
|
|
tokens: TokenStream<'a>,
|
|
}
|
|
|
|
#[derive(Debug, PartialEq)]
|
|
enum ParserError {
|
|
Eol
|
|
}
|
|
|
|
impl<'a> Parser<'a> {
|
|
fn parse_expression(&mut self, level: usize) -> Expression {
|
|
let mut left = self.parse_sub_expression(level).unwrap();
|
|
|
|
while let Ok(op) = self.parse_operator() {
|
|
let right = self.parse_sub_expression(level).unwrap();
|
|
|
|
left = Expression {
|
|
level,
|
|
value: ExpressionValue::Node(Node {
|
|
left: Box::new(left),
|
|
op,
|
|
right: Box::new(right),
|
|
})
|
|
}
|
|
}
|
|
|
|
left
|
|
}
|
|
|
|
fn parse_sub_expression(&mut self, level: usize) -> Result<Expression, ParserError> {
|
|
match self.tokens.next() {
|
|
Some(Token::Litteral(lit)) => Ok(Expression{ level, value: ExpressionValue::Litteral(lit) }),
|
|
Some(Token::OpeningParenthese) => Ok(self.parse_expression(level + 1)),
|
|
Some(token) => panic!("unexpected token {:?}, expected litteral or opening brance", token),
|
|
None => return Err(ParserError::Eol)
|
|
}
|
|
}
|
|
|
|
fn parse_operator(&mut self) -> Result<Operator, ParserError> {
|
|
match self.tokens.next() {
|
|
Some(Token::Add) => Ok(Operator::Add),
|
|
Some(Token::Mul) => Ok(Operator::Mul),
|
|
Some(Token::ClosingParenthese) | None => return Err(ParserError::Eol),
|
|
Some(token) => panic!("unexpected token {:?} expected operator", token),
|
|
}
|
|
}
|
|
|
|
}
|
|
|
|
impl FromStr for Expression {
|
|
type Err = ();
|
|
fn from_str(s: &str) -> Result<Self, Self::Err> {
|
|
let expr_str = s.replace(' ', "");
|
|
Ok(Parser {
|
|
tokens: TokenStream::new(&expr_str),
|
|
}.parse_expression(0))
|
|
|
|
}
|
|
}
|
|
|
|
|
|
impl Expression {
|
|
fn compute(&self) -> u64 {
|
|
match &self.value {
|
|
ExpressionValue::Litteral(lit) => *lit,
|
|
ExpressionValue::Node(Node { left, op, right }) => match op {
|
|
Operator::Add => left.compute() + right.compute(),
|
|
Operator::Mul => left.compute() * right.compute(),
|
|
}
|
|
}
|
|
}
|
|
|
|
fn is_node(&self) -> bool {
|
|
if let ExpressionValue::Node(_) = self.value {
|
|
true
|
|
} else {
|
|
false
|
|
}
|
|
}
|
|
|
|
fn unwrap_node(self) -> Node {
|
|
if let ExpressionValue::Node(node) = self.value {
|
|
node
|
|
} else {
|
|
panic!("tried to unwrap node on litteral expr")
|
|
}
|
|
}
|
|
|
|
/// Rotate the binary tree nodes to apply wanted precedence
|
|
/// To keep the precendence of parentheses grouping, rotation happens
|
|
/// only if the group level is the same.
|
|
/// + *
|
|
/// / \ / \
|
|
/// * 3 -> becomes -> 1 +
|
|
/// / \ / \
|
|
/// 1 2 2 3
|
|
fn apply_precedence(self, op: &Operator) -> Expression {
|
|
if self.is_node() {
|
|
let level = self.level;
|
|
let node = self.unwrap_node();
|
|
if &node.op == op && node.left.is_node() && level == node.left.level {
|
|
let left_child = node.left.unwrap_node();
|
|
Expression {
|
|
level,
|
|
value: ExpressionValue::Node(Node {
|
|
left: Box::new(left_child.left.apply_precedence(op)),
|
|
right: Box::new(Expression {
|
|
level,
|
|
value: ExpressionValue::Node(Node {
|
|
op: node.op,
|
|
left: left_child.right,
|
|
right: node.right
|
|
})
|
|
}.apply_precedence(op)),
|
|
op: left_child.op,
|
|
})
|
|
}.apply_precedence(op)
|
|
} else {
|
|
Expression {
|
|
level,
|
|
value: ExpressionValue::Node(Node {
|
|
op: node.op,
|
|
left: Box::new(node.left.apply_precedence(&op)),
|
|
right: Box::new(node.right.apply_precedence(&op))
|
|
})
|
|
}
|
|
}
|
|
} else {
|
|
self
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
pub fn part1<F: BufRead> (input: F) {
|
|
let sum: u64 = input.lines()
|
|
.map(|line| line.unwrap().parse::<Expression>().unwrap().compute())
|
|
.sum();
|
|
|
|
println!("{}", sum);
|
|
}
|
|
|
|
|
|
pub fn part2<F: BufRead> (input: F) {
|
|
let sum: u64 = input.lines()
|
|
.map(|line| line.unwrap().parse::<Expression>().unwrap().apply_precedence(&Operator::Add).compute())
|
|
.sum();
|
|
|
|
println!("{}", sum);
|
|
}
|
|
|
|
|
|
#[cfg(test)]
|
|
mod test {
|
|
use super::*;
|
|
|
|
#[test]
|
|
pub fn test_parse_node() {
|
|
let input = "2 * 3 + (4 * 5)";
|
|
let expected = Expression {
|
|
level: 0,
|
|
value: ExpressionValue::Node(Node {
|
|
left: Box::new(Expression {
|
|
level: 0,
|
|
value: ExpressionValue::Node(Node {
|
|
left: Box::new(Expression {
|
|
level: 0,
|
|
value: ExpressionValue::Litteral(2)
|
|
}),
|
|
op: Operator::Mul,
|
|
right: Box::new(Expression {
|
|
level: 0,
|
|
value: ExpressionValue::Litteral(3)
|
|
}),
|
|
})
|
|
}),
|
|
op: Operator::Add,
|
|
right: Box::new(Expression {
|
|
level: 1,
|
|
value: ExpressionValue::Node(Node {
|
|
left: Box::new(Expression {
|
|
level: 1,
|
|
value: ExpressionValue::Litteral(4)
|
|
}),
|
|
op: Operator::Mul,
|
|
right: Box::new(Expression {
|
|
level: 1,
|
|
value: ExpressionValue::Litteral(5)
|
|
}),
|
|
})
|
|
}),
|
|
})
|
|
};
|
|
assert_eq!(expected, input.parse().unwrap());
|
|
}
|
|
|
|
#[test]
|
|
pub fn test_parse_lit() {
|
|
let test_cases = &[("2", 2, 0), ("(83)", 83, 1)];
|
|
for (input, expected, level) in test_cases {
|
|
let expected = Expression {
|
|
level: *level,
|
|
value: ExpressionValue::Litteral(*expected)
|
|
};
|
|
assert_eq!(expected, input.parse::<Expression>().unwrap());
|
|
}
|
|
}
|
|
|
|
#[test]
|
|
pub fn test_compute() {
|
|
let test_cases = &[
|
|
("1 + 2 * 3 + 4 * 5 + 6", 71),
|
|
("1 + (2 * 3) + (4 * (5 + 6))", 51),
|
|
("2 * 3 + (4 * 5)", 26),
|
|
("5 + (8 * 3 + 9 + 3 * 4 * 3)", 437),
|
|
("5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))", 12_240),
|
|
("((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2", 13_632),
|
|
];
|
|
for (input, expected) in test_cases {
|
|
assert_eq!(*expected, input.parse::<Expression>().unwrap().compute());
|
|
}
|
|
}
|
|
|
|
#[test]
|
|
pub fn test_precedence() {
|
|
let test_cases = &[
|
|
("1 + 2 * 3 + 4 * 5 + 6", 231),
|
|
("1 + (2 * 3) + (4 * (5 + 6))", 51),
|
|
("2 * 3 + (4 * 5)", 46),
|
|
("5 + (8 * 3 + 9 + 3 * 4 * 3)", 1445),
|
|
("5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))", 669_060),
|
|
("((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2", 23_340),
|
|
("8 * 3 + 9 + 3 * 4 * 3", 1440),
|
|
];
|
|
for (input, expected) in test_cases {
|
|
let expression = input.parse::<Expression>().unwrap();
|
|
println!("{:#?}", expression);
|
|
let expression = expression.apply_precedence(&Operator::Add);
|
|
println!("{:#?}", expression);
|
|
assert_eq!(*expected, expression.compute());
|
|
}
|
|
}
|
|
}
|