Advent of Code 2020 day18
37666 단어 Rustadventofcodetech
part1
1 + 2 * 3 + 4 * 5 + 6
1 + (2 * 3) + (4 * (5 + 6))
과 같은 입력을 제공합니다.수치 계산이지만 일반적인 사칙 연산과 달리 연산자의 순서도 다르다.*
는 +
보다 우선하지 않고 왼쪽에서 오른쪽으로 차례대로 평가하며 괄호만 우선한다.상기 예 중의 첫 번째
1 + 2 * 3 + 4 * 5 + 6
= 3 * 3 + 4 * 5 + 6
= 9 + 4 * 5 + 6
= 13 * 5 + 6
= 65 + 6
= 71
두 번째 예는 1 + (2 * 3) + (4 * (5 + 6))
= 1 + (2 * 3) + (4 * 11)
= 1 + (2 * 3) + 44
= 1 + 6 + 44
= 7 + 44
= 51
의 상황.이 법칙에 따라 모든 공식의 결과의 합을 계산한다.이런 문제.괄호로 둘러싸인 부분을 잘 귀속적으로 처리할 수 있다면 문제없을 것 같다.여기
expression.chars()
에서 Chars
를 얻어 매개 변수에 넣고 한 글자 한 글자 읽으며 회귀에서 되돌아와도 계속 처리할 수 있다.그리고 연산자가 나올 때마다 그 방법의call에 나타난 수치를 계산해서 결과를 돌려주면 된다.
impl Solution {
fn new(inputs: Vec<String>) -> Self {
Self { inputs }
}
fn solve_1(&self) -> u64 {
self.inputs
.iter()
.map(|s| Solution::evaluate(s))
.sum()
}
fn evaluate(expression: &str) -> u64 {
let mut chars = expression.chars();
Solution::helper(&mut chars)
}
fn helper(chars: &mut Chars) -> u64 {
let (mut op, mut n) = ('+', 0);
let mut ret = 0;
while let Some(c) = chars.next() {
match c {
'0'..='9' => n = (c as u8 - b'0') as u64,
'+' | '*' => {
ret = if op == '+' { ret + n } else { ret * n };
n = 0;
op = c;
}
'(' => n = Solution::helper(chars),
')' => break,
_ => {}
}
}
if op == '+' {
ret + n
} else {
ret * n
}
}
}
part2
이번에
+
는 비*
가 우선하는 법칙에 따라 계산한다.이 경우 매번 처리할 수 없기 때문에 당분간
(operator, oprand)
의 조합을 Vec
에 삽입하고 마지막으로 계산 처리를 한다.#[derive(Copy, Clone)]
enum Op {
Add,
Mul,
}
impl Solution {
fn helper(chars: &mut Chars, advanced: bool) -> u64 {
let mut v: Vec<(Op, u64)> = Vec::new();
let mut op = Op::Mul;
while let Some(c) = chars.next() {
match c {
'0'..='9' => v.push((op, (c as u8 - b'0') as u64)),
'+' => op = Op::Add,
'*' => op = Op::Mul,
'(' => v.push((op, Solution::helper(chars, advanced))),
')' => break,
_ => {}
}
}
...
}
}
파트1의 경우 처음부터 이것Vec
을 보고 순서대로 처리한다.파트2의 경우 Stack으로 처리합니다.마지막 요소를 찾아내는 동시에 +
라면 이전의 것과 함께 *
하면 답과 곱한다. if advanced {
let mut ret = 1;
while let Some(last) = v.pop() {
match last.0 {
Op::Add => {
if let Some(prev) = v.last_mut() {
prev.1 += last.1;
}
}
Op::Mul => ret *= last.1,
}
}
ret
} else {
v.iter().fold(1, |acc, x| match x.0 {
Op::Add => acc + x.1,
Op::Mul => acc * x.1,
})
}
code
use std::io::{BufRead, BufReader};
use std::str::Chars;
struct Solution {
inputs: Vec<String>,
}
#[derive(Copy, Clone)]
enum Op {
Add,
Mul,
}
impl Solution {
fn new(inputs: Vec<String>) -> Self {
Self { inputs }
}
fn solve_1(&self) -> u64 {
self.inputs
.iter()
.map(|s| Solution::evaluate(s, false))
.sum()
}
fn solve_2(&self) -> u64 {
self.inputs
.iter()
.map(|s| Solution::evaluate(s, true))
.sum()
}
fn evaluate(expression: &str, advanced: bool) -> u64 {
let mut chars = expression.chars();
Solution::helper(&mut chars, advanced)
}
fn helper(chars: &mut Chars, advanced: bool) -> u64 {
let mut v: Vec<(Op, u64)> = Vec::new();
let mut op = Op::Mul;
while let Some(c) = chars.next() {
match c {
'0'..='9' => v.push((op, (c as u8 - b'0') as u64)),
'+' => op = Op::Add,
'*' => op = Op::Mul,
'(' => v.push((op, Solution::helper(chars, advanced))),
')' => break,
_ => {}
}
}
if advanced {
let mut ret = 1;
while let Some(last) = v.pop() {
match last.0 {
Op::Add => {
if let Some(prev) = v.last_mut() {
prev.1 += last.1;
}
}
Op::Mul => ret *= last.1,
}
}
ret
} else {
v.iter().fold(1, |acc, x| match x.0 {
Op::Add => acc + x.1,
Op::Mul => acc * x.1,
})
}
}
}
fn main() {
let solution = Solution::new(
BufReader::new(std::io::stdin().lock())
.lines()
.filter_map(|line| line.ok())
.collect(),
);
println!("{}", solution.solve_1());
println!("{}", solution.solve_2());
}
Reference
이 문제에 관하여(Advent of Code 2020 day18), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://zenn.dev/sugyan/articles/640d4a07c854e8텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)