main.rs

// Source: https://blog.jcoglan.com/2020/05/12/controlling-mutation-with-types/

use std::io;
use std::mem;
use std::str::Chars;

#[derive(Default)]
struct Stack<T> {
    head: T,
    rest: Vec<T>,
}

impl<T> Stack<T> {
    fn new(head: T) -> Stack<T> {
        Stack { head, rest: vec![] }
    }

    fn push(mut self, item: T) -> Stack<T> {
        let head = mem::replace(&mut self.head, item);
        self.rest.push(head);
        self
    }

    /*
    fn pop(&mut self) -> T {
        if let Some(item) = self.rest.pop() {
            mem::replace(&mut self.head, item)
        } else {
            panic!("Stack is empty")
        }
    }
    */

    fn pop(mut self) -> (T, Option<Stack<T>>) {
        let head = self.head;
        if let Some(item) = self.rest.pop() {
            self.head = item;
            (head, Some(self))
        } else {
            (head, None)
        }
    }

    fn with_item<F>(&mut self, item: T, f: F) -> T where
        F: FnOnce(&mut Stack<T>),
        T: Default
    {
        let stack = mem::take(self);

        let mut pushed_stack = stack.push(item);
        f(&mut pushed_stack);
        let (head, popped_stack) = pushed_stack.pop();

        if let Some(mut stack) = popped_stack {
            mem::swap(self, &mut stack);
        } else {
            panic!("Stack is empty")
        }

        head
    }

    fn last_mut(&mut self) -> &mut T {
        &mut self.head
    }
}

#[derive(Debug)]
enum Expr {
    List(Vec<Expr>),
    Digit(u32),
}

impl Expr {
    fn from_str(string: &str) -> Vec<Expr> {
        let mut stack = Stack::new(vec![]);
        parse_expr(&mut stack, &mut string.chars());
        stack.pop().0
    }
}

fn parse_expr(stack: &mut Stack<Vec<Expr>>, chars: &mut Chars) {
    while let Some(c) = chars.next() {
        match c {
            '['       => push_list(stack, chars, |st, ch| parse_expr(st, ch)),
            '0'..='9' => push_digit(stack, c),
            ']'       => break,
            _         => {}
        }
    }
}

fn push_list<F>(stack: &mut Stack<Vec<Expr>>, chars: &mut Chars, f: F) where
    F: FnOnce(&mut Stack<Vec<Expr>>, &mut Chars)
{
    // Push the new empty vector onto the top of the stack, ...
    let list = stack.with_item(vec![], |inner_stack| {
        // ... run the processing, ...
        f(inner_stack, chars);
    });

    // ... and finally push the result back down.
    push_down(stack, Expr::List(list));
}

fn push_down(stack: &mut Stack<Vec<Expr>>, value: Expr) {
    stack.last_mut().push(value);
}

fn push_digit(stack: &mut Stack<Vec<Expr>>, c: char) {
    let value = Expr::Digit(c.to_digit(10).unwrap());
    push_down(stack, value);
}

fn main() -> io::Result<()> {
    let mut input = String::new();
    io::stdin().read_line(&mut input)?;

    let expr_list = Expr::from_str(input.trim());
    println!("Parsed expression: {:?}", expr_list);

    Ok(())
}