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 {
43                    0
44                } else {
45                    4
46                }
47            }
48            _ => 3,
49        }
50    }
51
52    fn consume(&mut self, char: u8) -> Result<(), String> {
53        match char {
54            b'(' | b')' | b'+' | b'*' => {
55                let this_operator_precedence = self.operator_precedence(char, false);
56                loop {
57                    if let Some(&operator) = self.operator_stack.last() {
58                        let top_of_stack_operator_precendence =
59                            self.operator_precedence(operator, true);
60
61                        if this_operator_precedence > top_of_stack_operator_precendence {
62                            self.operator_stack.push(char);
63                            break;
64                        } else {
65                            self.operator_stack.pop();
66                            if !matches!(operator, b'(' | b')') {
67                                self.postfix_expression.push(operator);
68                            } else if operator == b')' {
69                                // Pop everything off the operator stack until we see the matching left parentheses:
70                                while let Some(operator) = self.operator_stack.pop() {
71                                    if operator == b'(' {
72                                        break;
73                                    } else if operator != b')' {
74                                        self.postfix_expression.push(operator);
75                                    }
76                                }
77                            }
78                        }
79                    } else {
80                        self.operator_stack.push(char);
81                        break;
82                    }
83                }
84                Ok(())
85            }
86            b'0'..=b'9' => {
87                self.postfix_expression.push(char);
88                Ok(())
89            }
90            b' ' => Ok(()),
91            _ => Err(format!("Invalid char: {char}")),
92        }
93    }
94
95    fn finish(&mut self) -> Result<CalculatorValue, String> {
96        let on_error = || "Unbalanced operators".to_string();
97        while let Some(operator) = self.operator_stack.pop() {
98            if !matches!(operator, b'(' | b')') {
99                self.postfix_expression.push(operator);
100            }
101        }
102
103        for &c in self.postfix_expression.iter() {
104            match c {
105                b'+' | b'*' => {
106                    let o1 = self.operand_stack.pop().ok_or_else(on_error)?;
107                    let o2 = self.operand_stack.pop().ok_or_else(on_error)?;
108                    let result = if c == b'+' { o1 + o2 } else { o1 * o2 };
109                    self.operand_stack.push(result);
110                }
111                _ => {
112                    let digit_value = c - b'0';
113                    self.operand_stack.push(CalculatorValue::from(digit_value));
114                }
115            }
116        }
117
118        self.operand_stack.last().copied().ok_or_else(on_error)
119    }
120}
121
122pub fn solve(input: &Input) -> Result<u64, String> {
123    let mut parser = Parser::new(input.is_part_two());
124    input
125        .text
126        .lines()
127        .map(|line| {
128            parser.reset();
129            for char in line.bytes() {
130                parser.consume(char)?;
131            }
132            parser.finish()
133        })
134        .sum::<Result<CalculatorValue, String>>()
135}
136
137#[test]
138pub fn tests() {
139    use crate::input::{test_part_one, test_part_two};
140
141    let example = "1 + 2 * 3 + 4 * 5 + 6";
142    test_part_one!(example => 71);
143    test_part_two!(example => 231);
144
145    let real_input = include_str!("day18_input.txt");
146    test_part_one!(real_input => 16_332_191_652_452);
147    test_part_two!(real_input => 351_175_492_232_654);
148}
advent_of_code/year2020/day18.rs

advent_of_code/year2020/
day18.rs
