AoC 2020 Day 18 — Shunting-Yard Algorithm with Rust
This is part of a series we did on the Advent of Code 2020 problems. You can see a list of all the problems we wrote about here.
If you are a fan of AoC, and had fun working on these problems, it is likely that you would be a good fit with our team. Our engineering team had a blast with it, as we like to be challenged with hard problems. If you like what you see, we are constantly looking for great talent, please consider joining us!
Day 18’s puzzle involved helping a child with their maths homework, unfortunately, this “maths” has different rules. The homework is to evaluate various expressions containing addition (+) multiplication (*) and parentheses ((...)). Here are some example expressions:
2 * 3 + (4 * 5)
5 + (7 * 7) + (2 + (1 + 6))
((2 + 4 * 9 + 2) * (6 + 1 * (8 + 6)) + 6) + 3 + 4 * 7Parentheses have their usual meaning and indicate the expression inside them must be evaluated before they can be used in other expressions. What makes this maths special is the operator precedence. Like the other AoC problems, the problem is split into two parts. In part 1, both operators have the same precedence. In part 2, addition has a higher precedence than multiplication.
In this post, I will be showing my Rust solution to part 2, which is an extension of part 1.
Reverse Polish Notation
We are most familiar with infix notation, in which an operator is placed between its operands. Reverse Polish notation (RPN), however, places operators after their operands.
Infix notation: 3 + 4
RPN notaiton: 3 4 +What is interesting about RPN is that we do not need parentheses to express precedence. This is because operators come directly after their second operand. Consider the slightly more complicated expression 3 4 5 * +. This is equivalent to 3 + (4 * 5) and would be evaluated as follows.
3 4 5 * +
3 (4 5 *) +
3 20 +
23RPN expressions can be evaluated using a stack. This is done by going through each token. If the token is a number, add it to the stack. If the token is an operator, pop the last two elements from the stack to use as operands and add push the result to the stack. If the expression is well formed, you should have one element left on the stack at the end. Let’s look at the evaluation of the expression 7 2 5 + 7 * 4 * + 6 + .
+---------------+------------+-------------------------+
| Current Token | Stack | Action |
+---------------+------------+-------------------------+
| 7 | [] | Push 7 |
+---------------+------------+-------------------------+
| 2 | [7] | Push 2 |
+---------------+------------+-------------------------+
| 5 | [7, 2] | Push 5 |
+---------------+------------+-------------------------+
| + | [7, 2, 5] | Pop 5, 2 and Push 7 |
+---------------+------------+-------------------------+
| 7 | [7, 7] | Push 7 |
+---------------+------------+-------------------------+
| * | [7, 7, 7] | Pop 7, 7 and Push 49 |
+---------------+------------+-------------------------+
| 4 | [7, 49] | Push 4 |
+---------------+------------+-------------------------+
| * | [7, 49, 4] | Pop 4, 49 and Push 196 |
+---------------+------------+-------------------------+
| + | [7, 196] | Pop 196, 7 and Push 203 |
+---------------+------------+-------------------------+
| 6 | [203] | Push 6 |
+---------------+------------+-------------------------+
| + | [203, 6] | Pop 6, 203 and Push 209 |
+---------------+------------+-------------------------+
| END | [209] | Result is 209 |
+---------------+------------+-------------------------+Here is my Rust implementation to evaluate RPN expressions.
fn evaluate_rpn(input: &Vec<char>) -> u64 {
/* Evaluates statement in RPN notation */
let mut stack: Vec<u64> = vec![]; for token in input.into_iter() {
match token {
'*' => {
let first: u64 = stack.pop().unwrap();
let second: u64 = stack.pop().unwrap();
stack.push(first * second);
},
'+' => {
let first: u64 = stack.pop().unwrap();
let second: u64 = stack.pop().unwrap();
stack.push(first + second);
},
_ => {
stack.push(token.to_digit(10).unwrap() as u64);
},
}
}
assert!(stack.len() == 1);
return stack[0]
}
Now we need some way to convert the infix expressions to RPN. This can be done with Dijkstra’s shunting-yard algorithm.
Shunting-Yard Algorithm
The shunting-yard algorithm is a way to parse expressions in infix notation and can return the expression in RPN. The full details and pseudocode of the algorithms can be found here. For this challenge, we need a simplified version of the algorithm because we only have two operators with precedence differences. We also don’t need to consider associativity of operators because both operators are left associative. Here is my Rust function to do this.
fn shunting_yard(input: &str) -> Vec<char> {
/* Shunting yard algorithm. */
let mut operator_stack: Vec<char> = Vec::new();
let mut output_queue: Vec<char> = Vec::new();
for token in input.chars() {
if token == ' ' {
continue;
} else if token.is_digit(10) {
output_queue.push(token);
} else if token == '+' {
while operator_stack.last() == Some(&'+') {
output_queue.push(operator_stack.pop().unwrap());
}
operator_stack.push(token);
} else if token == '*' {
while operator_stack.last() == Some(&'+') ||
operator_stack.last() == Some(&'*') {
output_queue.push(operator_stack.pop().unwrap());
}
operator_stack.push(token);
} else if token == '(' {
operator_stack.push(token);
} else if token == ')' {
while operator_stack.last() != Some(&'(') {
output_queue.push(operator_stack.pop().unwrap());
}
operator_stack.pop();
} else {
assert!(false);
}
}
while let Some(op) = operator_stack.pop() {
output_queue.push(op);
}
output_queue
}Putting it All Together
To get the puzzle solution. We convert each line to RPN and evaluate the results. These results are then summed together.
let res: u64 = lines.map(|line| evaluate_rpn(&shunting_yard(&line)))
.sum();The full code can be found here.
I hope you enjoyed reading about this problem. I had fun working on it, and I would encourage you to take a look at the other entries in this series. If you are passionate about software engineering and solving difficult problems, we are constantly hiring for talented engineers.
