advent_of_code/year2020/
day18.rs

1use crate::input::Input;
2
3type CalculatorValue = u64;
4
5struct Parser {
6    operand_stack: Vec<CalculatorValue>,
7    operator_stack: Vec<u8>,
8    postfix_expression: Vec<u8>,
9    addition_precedence: u8,
10    multiplication_precedence: u8,
11}
12
13impl Parser {
14    fn new(addition_has_higher_precedence: bool) -> Self {
15        let (addition_precedence, multiplication_precedence) = if addition_has_higher_precedence {
16            (2, 1)
17        } else {
18            (1, 1)
19        };
20
21        Self {
22            operand_stack: Vec::with_capacity(64),
23            operator_stack: Vec::with_capacity(64),
24            postfix_expression: Vec::with_capacity(64),
25            addition_precedence,
26            multiplication_precedence,
27        }
28    }
29
30    fn reset(&mut self) {
31        self.operand_stack.clear();
32        self.operator_stack.clear();
33        self.postfix_expression.clear();
34    }
35
36    const fn operator_precedence(&self, char: u8, top_of_stack: bool) -> u8 {
37        match char {
38            b'+' => self.addition_precedence,
39            b'*' => self.multiplication_precedence,
40            b'(' => {
41                // '(' has lowest precedence when top of stack:
42                if top_of_stack { 0 } else { 4 }
43            }
44            _ => 3,
45        }
46    }
47
48    fn consume(&mut self, char: u8) -> Result<(), String> {
49        match char {
50            b'(' | b')' | b'+' | b'*' => {
51                let this_operator_precedence = self.operator_precedence(char, false);
52                loop {
53                    if let Some(&operator) = self.operator_stack.last() {
54                        let top_of_stack_operator_precendence =
55                            self.operator_precedence(operator, true);
56
57                        if this_operator_precedence > top_of_stack_operator_precendence {
58                            self.operator_stack.push(char);
59                            break;
60                        } else {
61                            self.operator_stack.pop();
62                            if !matches!(operator, b'(' | b')') {
63                                self.postfix_expression.push(operator);
64                            } else if operator == b')' {
65                                // Pop everything off the operator stack until we see the matching left parentheses:
66                                while let Some(operator) = self.operator_stack.pop() {
67                                    if operator == b'(' {
68                                        break;
69                                    } else if operator != b')' {
70                                        self.postfix_expression.push(operator);
71                                    }
72                                }
73                            }
74                        }
75                    } else {
76                        self.operator_stack.push(char);
77                        break;
78                    }
79                }
80                Ok(())
81            }
82            b'0'..=b'9' => {
83                self.postfix_expression.push(char);
84                Ok(())
85            }
86            b' ' => Ok(()),
87            _ => Err(format!("Invalid char: {char}")),
88        }
89    }
90
91    fn finish(&mut self) -> Result<CalculatorValue, String> {
92        let on_error = || "Unbalanced operators".to_string();
93        while let Some(operator) = self.operator_stack.pop() {
94            if !matches!(operator, b'(' | b')') {
95                self.postfix_expression.push(operator);
96            }
97        }
98
99        for &c in self.postfix_expression.iter() {
100            match c {
101                b'+' | b'*' => {
102                    let o1 = self.operand_stack.pop().ok_or_else(on_error)?;
103                    let o2 = self.operand_stack.pop().ok_or_else(on_error)?;
104                    let result = if c == b'+' { o1 + o2 } else { o1 * o2 };
105                    self.operand_stack.push(result);
106                }
107                _ => {
108                    let digit_value = c - b'0';
109                    self.operand_stack.push(CalculatorValue::from(digit_value));
110                }
111            }
112        }
113
114        self.operand_stack.last().copied().ok_or_else(on_error)
115    }
116}
117
118pub fn solve(input: &Input) -> Result<u64, String> {
119    let mut parser = Parser::new(input.is_part_two());
120    input
121        .text
122        .lines()
123        .map(|line| {
124            parser.reset();
125            for char in line.bytes() {
126                parser.consume(char)?;
127            }
128            parser.finish()
129        })
130        .sum::<Result<CalculatorValue, String>>()
131}
132
133#[test]
134pub fn tests() {
135    let example = "1 + 2 * 3 + 4 * 5 + 6";
136    test_part_one!(example => 71);
137    test_part_two!(example => 231);
138
139    let real_input = include_str!("day18_input.txt");
140    test_part_one!(real_input => 16_332_191_652_452);
141    test_part_two!(real_input => 351_175_492_232_654);
142}
advent_of_code/year2020/day18.rs

advent_of_code/year2020/
day18.rs
