Програмиране с Rust

Курс във Факултета по Математика и Информатика към СУ

Решение на Reversible Interpreter от Деян Горанов

Обратно към всички решения

Към профила на Деян Горанов

Резултати

  • 15 точки от тестове
  • 0 бонус точки
  • 15 точки общо
  • 12 успешни тест(а)
  • 0 неуспешни тест(а)

Код

//! We have some constants and 3 private types:
//! * `const *_INSTR` - those are used so as not to harcode instruction names
//! * `enum BinOp` - a binary operation, helps avoid repetition in `Cmd`
//! and `Action`
//! * `enum Cmd` - a command, the result of parsing an instruction
//! * `enum Action` - the action taken for executing a `Cmd`, holds all
//! necessary data to undo the `Cmd`
use std::{collections::VecDeque, str::FromStr};
const PUSH_INSTR: &str = "PUSH";
const POP_INSTR: &str = "POP";
const ADD_INSTR: &str = "ADD";
const MUL_INSTR: &str = "MUL";
const SUB_INSTR: &str = "SUB";
const DIV_INSTR: &str = "DIV";
#[derive(Clone, Debug)]
enum BinOp {
Add,
Mul,
Sub,
Div,
}
struct ParseBinOpError;
enum BinOpCalcError {
DivideByZero,
}
impl BinOp {
fn to_instr(&self) -> String {
match self {
BinOp::Add => ADD_INSTR,
BinOp::Mul => MUL_INSTR,
BinOp::Sub => SUB_INSTR,
BinOp::Div => DIV_INSTR,
}
.into()
}
fn calc(&self, x: i32, y: i32) -> Result<i32, BinOpCalcError> {
match self {
BinOp::Add => Ok(x + y),
BinOp::Mul => Ok(x * y),
BinOp::Sub => Ok(x - y),
BinOp::Div => {
if y == 0 {
Err(BinOpCalcError::DivideByZero)
} else {
Ok(x / y)
}
}
}
}
}
impl FromStr for BinOp {
type Err = ParseBinOpError;
fn from_str(input: &str) -> Result<Self, Self::Err> {
match input {
ADD_INSTR => Ok(BinOp::Add),
MUL_INSTR => Ok(BinOp::Mul),
SUB_INSTR => Ok(BinOp::Sub),
DIV_INSTR => Ok(BinOp::Div),
_ => Err(ParseBinOpError),
}
}
}
enum Cmd {
Push(i32),
Pop,
BinOp(BinOp),
}
struct ParseCmdError;
enum CmdExecError {
StackUnderflow,
Calc(BinOpCalcError),
}
impl From<BinOpCalcError> for CmdExecError {
fn from(e: BinOpCalcError) -> Self {
CmdExecError::Calc(e)
}
}
impl Cmd {
fn exec_with(self, mut stack: Vec<i32>) -> Result<(Vec<i32>, Action), CmdExecError> {
let mut pop_stack = || stack.pop().ok_or(CmdExecError::StackUnderflow);
let action = match self {
Cmd::Push(i) => {
stack.push(i);
Action::Push(i)
}
Cmd::Pop => {
let x = pop_stack()?;
Action::Pop(x)
}
Cmd::BinOp(op) => {
let x = pop_stack()?;
let y = pop_stack()?;
stack.push(op.calc(x, y)?);
Action::BinOp(op, x, y)
}
};
Ok((stack, action))
}
}
impl FromStr for Cmd {
type Err = ParseCmdError;
fn from_str(input: &str) -> Result<Self, Self::Err> {
// will be able to ditch the instantly-invoked closure in the future:
// https://doc.rust-lang.org/std/option/struct.NoneError.html
// https://doc.rust-lang.org/nightly/unstable-book/language-features/try-blocks.html
|| -> Option<Self> {
let mut tokens = input.split_whitespace();
let name = &*tokens.next()?.to_ascii_uppercase();
let cmd = match name {
PUSH_INSTR => Some(Cmd::Push(tokens.next()?.parse().ok()?)),
POP_INSTR => Some(Cmd::Pop),
_ => Some(Cmd::BinOp(input.parse().ok()?)),
};
if tokens.next().is_none() {
cmd
} else {
None
}
}()
.ok_or(ParseCmdError)
}
}
// The action taken for execuring a `Cmd`.
// Each variant contains the needed information to undo the corresponding `Cmd`.
#[derive(Clone, Debug)]
enum Action {
Push(i32),
Pop(i32),
BinOp(BinOp, i32, i32),
}
impl Action {
fn to_instr(&self) -> String {
match self {
Action::Push(i) => format!("{} {}", PUSH_INSTR, i),
Action::Pop(_) => POP_INSTR.into(),
Action::BinOp(op, _, _) => op.to_instr(),
}
}
// returns `None` if the stack is empty
// and the `Action` expects it not to be
fn undo_on(&self, mut stack: Vec<i32>) -> Option<Vec<i32>> {
match *self {
Action::Push(_) => {
stack.pop()?;
}
Action::Pop(x) => stack.push(x),
Action::BinOp(_, x, y) => {
stack.pop()?;
stack.push(y);
stack.push(x);
}
}
Some(stack)
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum RuntimeError {
DivideByZero,
StackUnderflow,
InvalidCommand,
NoInstructions,
}
impl From<ParseCmdError> for RuntimeError {
fn from(_: ParseCmdError) -> Self {
RuntimeError::InvalidCommand
}
}
impl From<CmdExecError> for RuntimeError {
fn from(err: CmdExecError) -> Self {
match err {
CmdExecError::Calc(BinOpCalcError::DivideByZero) => RuntimeError::DivideByZero,
CmdExecError::StackUnderflow => RuntimeError::StackUnderflow,
}
}
}
#[derive(Debug, Default)]
pub struct Interpreter {
pub instructions: VecDeque<String>,
pub stack: Vec<i32>,
prev_actions: Vec<Action>,
}
impl Interpreter {
/// Конструира нов интерпретатор с празен стек и никакви инструкции.
///
/// ```
/// use solution::Interpreter;
/// use std::collections::VecDeque;
///
/// let interpreter = Interpreter::new();
/// assert_eq!(interpreter.instructions, VecDeque::new());
/// assert_eq!(interpreter.stack, vec![]);
/// ```
pub fn new() -> Self {
Self {
instructions: VecDeque::new(),
stack: vec![],
prev_actions: vec![],
}
}
/// Добавя инструкции от дадения списък към края на `instructions`.
/// Инструкциите не се интерпретират, само се записват.
/// Пример:
///
/// ```
/// use solution::Interpreter;
///
/// let mut interpreter = Interpreter::new();
/// let ins = [
/// "PUSH 1",
/// "PUSH 2",
/// "ADD",
/// ];
///
/// interpreter.add_instructions(&ins);
///
/// assert_eq!(interpreter.instructions, ins);
/// assert_eq!(interpreter.stack, vec![]);
/// ```
pub fn add_instructions(&mut self, instructions: &[&str]) {
self.instructions
.extend(instructions.iter().map(|&s| s.into()));
}
/// Връща mutable reference към инструкцията, която ще се изпълни при
/// следващия `.forward()` -- първата в списъка/дека.
///
/// ```
/// use solution::Interpreter;
///
/// let mut interpreter = Interpreter::new();
/// assert_eq!(interpreter.current_instruction(), None);
///
/// let ins = [
/// "PUSH 1",
/// "PUSH 2",
/// "ADD",
/// ];
/// interpreter.add_instructions(&ins);
///
/// assert_eq!(interpreter.current_instruction(), Some(&mut String::from("PUSH 1")));
/// ```
pub fn current_instruction(&mut self) -> Option<&mut String> {
self.instructions.front_mut()
}
/// Интерпретира първата инструкция в `self.instructions` по правилата
/// описани по-горе. Записва някаква информация за да може успешно да се
/// изпълни `.back()` в по-нататъшен момент.
///
/// Ако няма инструкции, връща `RuntimeError::NoInstructions`. Другите
/// грешки идват от обясненията по-горе.
///
pub fn forward(&mut self) -> Result<(), RuntimeError> {
let (new_stack, action) = self
.current_instruction()
.ok_or(RuntimeError::NoInstructions)?
.parse::<Cmd>()?
.exec_with(self.stack.clone())?;
self.instructions.pop_front();
self.stack = new_stack;
self.prev_actions.push(action);
Ok(())
}
/// Вика `.forward()` докато не свършат инструкциите (може и да се
/// имплементира по други начини, разбира се) или има грешка.
///
pub fn run(&mut self) -> Result<(), RuntimeError> {
loop {
match self.forward() {
Err(RuntimeError::NoInstructions) => return Ok(()),
Err(e) => return Err(e),
_ => (),
}
}
}
/// "Обръща" последно-изпълнената инструкция с `.forward()`. Това може да
/// се изпълнява отново и отново за всяка инструкция, изпълнена с
/// `.forward()` -- тоест, не пазим само последната инструкция, а
/// списък/стек от всичките досега.
///
/// Ако няма инструкция за връщане, очакваме
/// `RuntimeError::NoInstructions`.
///
pub fn back(&mut self) -> Result<(), RuntimeError> {
let action = self
.prev_actions
.pop()
.ok_or(RuntimeError::NoInstructions)?;
let new_stack = action.undo_on(self.stack.clone()).ok_or_else(|| {
// action undoing failed, so we return the action were it was
self.prev_actions.push(action.clone());
RuntimeError::StackUnderflow
})?;
self.instructions.push_front(action.to_instr());
self.stack = new_stack;
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_add_instructions_preserve_case() {
let mut interpreter = Interpreter::new();
let ins = ["PuSh 1", "pusH 2", "add"];
interpreter.add_instructions(&ins);
assert_eq!(interpreter.instructions, ins);
}
#[test]
fn test_adding_invalid_instructions_doesnt_fail() {
let mut interpreter = Interpreter::new();
let ins = ["PUSH", "PUSH 2 20", "ADD 20 200", "няма такова"];
interpreter.add_instructions(&ins);
assert_eq!(interpreter.instructions, ins);
}
#[test]
fn test_with_example() {
let mut interpreter = Interpreter::new();
let instructions = ["PUSH 0", "PUSH 42", "DIV"];
interpreter.add_instructions(&instructions);
assert_eq!(interpreter.instructions, instructions);
assert_eq!(interpreter.stack, []);
assert!(interpreter.forward().is_ok()); // PUSH 0
assert!(interpreter.forward().is_ok()); // PUSH 42
// Дотук добре:
assert_eq!(interpreter.instructions, ["DIV"]);
assert_eq!(interpreter.stack, [0, 42]);
assert_eq!(interpreter.forward(), Err(RuntimeError::DivideByZero));
assert_eq!(interpreter.instructions, ["DIV"]);
assert_eq!(interpreter.stack, [0, 42]);
// Опа, объркахме първата команда, дай назад
assert!(interpreter.back().is_ok());
assert!(interpreter.back().is_ok());
assert_eq!(interpreter.instructions, instructions);
assert_eq!(interpreter.stack, []);
if let Some(i) = interpreter.current_instruction() {
*i = String::from("PUSH 2");
}
assert!(interpreter.run().is_ok());
assert!(interpreter.instructions.is_empty());
assert_eq!(interpreter.stack, [21]);
}
#[test]
fn test_forward() {
let mut interpreter = Interpreter::new();
assert_eq!(interpreter.forward(), Err(RuntimeError::NoInstructions));
assert!(interpreter.instructions.is_empty());
assert_eq!(interpreter.stack, []);
interpreter.add_instructions(&["PUSH 7", "MUL"]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Err(RuntimeError::StackUnderflow));
assert_eq!(interpreter.instructions, ["MUL"]);
assert_eq!(interpreter.stack, [7]);
if let Some(i) = interpreter.current_instruction() {
*i = String::from("НЯМА");
}
assert_eq!(interpreter.forward(), Err(RuntimeError::InvalidCommand));
assert_eq!(interpreter.instructions, ["НЯМА"]);
assert_eq!(interpreter.stack, [7]);
}
#[test]
fn test_back() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&["PUSH 3", "PUSH 7", "MUL"]);
assert_eq!(interpreter.back(), Err(RuntimeError::NoInstructions));
assert!(interpreter.run().is_ok());
assert_eq!(interpreter.instructions, VecDeque::new());
assert_eq!(interpreter.stack, [21]);
assert!(interpreter.back().is_ok());
assert_eq!(interpreter.instructions, ["MUL"]);
assert_eq!(interpreter.stack, [3, 7]);
let mut check = |instr: &str, out| {
if let Some(i) = interpreter.current_instruction() {
*i = String::from(instr);
}
assert!(interpreter.run().is_ok());
assert_eq!(interpreter.instructions, VecDeque::new());
assert_eq!(interpreter.stack, [out]);
assert!(interpreter.back().is_ok());
assert_eq!(interpreter.instructions, [instr]);
assert_eq!(interpreter.stack, [3, 7]);
};
check("ADD", 10);
check("SUB", 4);
check("DIV", 2);
}
}

Лог от изпълнението

Compiling solution v0.1.0 (/tmp/d20210120-1538662-1x11ur8/solution)
    Finished test [unoptimized + debuginfo] target(s) in 2.48s
     Running target/debug/deps/solution_test-8916805fc40a2dab

running 12 tests
test solution_test::test_arg_number ... ok
test solution_test::test_arithmetic_back ... ok
test solution_test::test_arithmetic_basic ... ok
test solution_test::test_div_1 ... ok
test solution_test::test_div_2 ... ok
test solution_test::test_errors_1 ... ok
test solution_test::test_errors_2 ... ok
test solution_test::test_instructions_after_error ... ok
test solution_test::test_invalid_args ... ok
test solution_test::test_pop ... ok
test solution_test::test_push ... ok
test solution_test::test_restoring_instructions ... ok

test result: ok. 12 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

История (3 версии и 0 коментара)

Деян качи първо решение на 20.01.2021 16:08 (преди над 4 години)

Деян качи решение на 20.01.2021 16:45 (преди над 4 години)

//! We have some constants and 3 private types:
//! * `const *_INSTR` - those are used so as not to harcode instruction names
//! * `enum BinOp` - a binary operation, helps avoid repetition in `Cmd`
//! and `Action`
//! * `enum Cmd` - a command, the result of parsing an instruction
//! * `enum Action` - the action taken for executing a `Cmd`, holds all
//! necessary data to undo the `Cmd`
use std::{collections::VecDeque, str::FromStr};
const PUSH_INSTR: &str = "PUSH";
const POP_INSTR: &str = "POP";
const ADD_INSTR: &str = "ADD";
const MUL_INSTR: &str = "MUL";
const SUB_INSTR: &str = "SUB";
const DIV_INSTR: &str = "DIV";
#[derive(Clone, Debug)]
enum BinOp {
Add,
Mul,
Sub,
Div,
}
struct ParseBinOpError;
enum BinOpCalcError {
DivideByZero,
}
impl BinOp {
fn to_instr(&self) -> String {
match self {
BinOp::Add => ADD_INSTR,
BinOp::Mul => MUL_INSTR,
BinOp::Sub => SUB_INSTR,
BinOp::Div => DIV_INSTR,
}
.into()
}
fn calc(&self, x: i32, y: i32) -> Result<i32, BinOpCalcError> {
match self {
BinOp::Add => Ok(x + y),
BinOp::Mul => Ok(x * y),
BinOp::Sub => Ok(x - y),
BinOp::Div => {
if y == 0 {
Err(BinOpCalcError::DivideByZero)
} else {
Ok(x / y)
}
}
}
}
}
impl FromStr for BinOp {
type Err = ParseBinOpError;
fn from_str(input: &str) -> Result<Self, Self::Err> {
match input {
ADD_INSTR => Ok(BinOp::Add),
MUL_INSTR => Ok(BinOp::Mul),
SUB_INSTR => Ok(BinOp::Sub),
DIV_INSTR => Ok(BinOp::Div),
_ => Err(ParseBinOpError),
}
}
}
enum Cmd {
Push(i32),
Pop,
BinOp(BinOp),
}
struct ParseCmdError;
enum CmdExecError {
StackUnderflow,
Calc(BinOpCalcError),
}
impl From<BinOpCalcError> for CmdExecError {
fn from(e: BinOpCalcError) -> Self {
CmdExecError::Calc(e)
}
}
impl Cmd {
fn exec_with(self, mut stack: Vec<i32>) -> Result<(Vec<i32>, Action), CmdExecError> {
let mut pop_stack = || stack.pop().ok_or(CmdExecError::StackUnderflow);
let action = match self {
Cmd::Push(i) => {
stack.push(i);
Action::Push(i)
}
Cmd::Pop => {
let x = pop_stack()?;
Action::Pop(x)
}
Cmd::BinOp(op) => {
let x = pop_stack()?;
let y = pop_stack()?;
stack.push(op.calc(x, y)?);
Action::BinOp(op, x, y)
}
};
Ok((stack, action))
}
}
impl FromStr for Cmd {
type Err = ParseCmdError;
fn from_str(input: &str) -> Result<Self, Self::Err> {
// will be able to ditch the instantly-invoked closure in the future:
// https://doc.rust-lang.org/std/option/struct.NoneError.html
// https://doc.rust-lang.org/nightly/unstable-book/language-features/try-blocks.html
|| -> Option<Self> {
let mut tokens = input.split_whitespace();
let name = &*tokens.next()?.to_ascii_uppercase();
let cmd = match name {
PUSH_INSTR => Some(Cmd::Push(tokens.next()?.parse().ok()?)),
POP_INSTR => Some(Cmd::Pop),
_ => Some(Cmd::BinOp(input.parse().ok()?)),
};
if tokens.next().is_none() {
cmd
} else {
None
}
}()
.ok_or(ParseCmdError)
}
}
// The action taken for execuring a `Cmd`.
// Each variant contains the needed information to undo the corresponding `Cmd`.
#[derive(Clone, Debug)]
enum Action {
Push(i32),
Pop(i32),
BinOp(BinOp, i32, i32),
}
impl Action {
fn to_instr(&self) -> String {
match self {
Action::Push(i) => format!("{} {}", PUSH_INSTR, i),
Action::Pop(_) => POP_INSTR.into(),
Action::BinOp(op, _, _) => op.to_instr(),
}
}
// returns `None` if the stack is empty
// and the `Action` expects it not to be
fn undo_on(&self, mut stack: Vec<i32>) -> Option<Vec<i32>> {
match *self {
Action::Push(_) => {
stack.pop()?;
}
Action::Pop(x) => stack.push(x),
Action::BinOp(_, x, y) => {
stack.pop()?;
stack.push(y);
stack.push(x);
}
}
Some(stack)
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum RuntimeError {
DivideByZero,
StackUnderflow,
InvalidCommand,
NoInstructions,
}
impl From<ParseCmdError> for RuntimeError {
fn from(_: ParseCmdError) -> Self {
RuntimeError::InvalidCommand
}
}
impl From<CmdExecError> for RuntimeError {
fn from(err: CmdExecError) -> Self {
match err {
CmdExecError::Calc(BinOpCalcError::DivideByZero) => RuntimeError::DivideByZero,
CmdExecError::StackUnderflow => RuntimeError::StackUnderflow,
}
}
}
#[derive(Debug, Default)]
pub struct Interpreter {
pub instructions: VecDeque<String>,
pub stack: Vec<i32>,
prev_actions: Vec<Action>,
}
impl Interpreter {
/// Конструира нов интерпретатор с празен стек и никакви инструкции.
///
/// ```
/// use solution::Interpreter;
/// use std::collections::VecDeque;
///
/// let interpreter = Interpreter::new();
/// assert_eq!(interpreter.instructions, VecDeque::new());
/// assert_eq!(interpreter.stack, vec![]);
/// ```
pub fn new() -> Self {
Self {
instructions: VecDeque::new(),
stack: vec![],
prev_actions: vec![],
}
}
/// Добавя инструкции от дадения списък към края на `instructions`.
/// Инструкциите не се интерпретират, само се записват.
/// Пример:
///
/// ```
/// use solution::Interpreter;
///
/// let mut interpreter = Interpreter::new();
/// let ins = [
/// "PUSH 1",
/// "PUSH 2",
/// "ADD",
/// ];
///
/// interpreter.add_instructions(&ins);
///
/// assert_eq!(interpreter.instructions, ins);
/// assert_eq!(interpreter.stack, vec![]);
/// ```
pub fn add_instructions(&mut self, instructions: &[&str]) {
self.instructions
.extend(instructions.iter().map(|&s| s.into()));
}
/// Връща mutable reference към инструкцията, която ще се изпълни при
/// следващия `.forward()` -- първата в списъка/дека.
///
/// ```
/// use solution::Interpreter;
///
/// let mut interpreter = Interpreter::new();
/// assert_eq!(interpreter.current_instruction(), None);
///
/// let ins = [
/// "PUSH 1",
/// "PUSH 2",
/// "ADD",
/// ];
/// interpreter.add_instructions(&ins);
///
/// assert_eq!(interpreter.current_instruction(), Some(&mut String::from("PUSH 1")));
/// ```
pub fn current_instruction(&mut self) -> Option<&mut String> {
self.instructions.front_mut()
}
/// Интерпретира първата инструкция в `self.instructions` по правилата
/// описани по-горе. Записва някаква информация за да може успешно да се
/// изпълни `.back()` в по-нататъшен момент.
///
/// Ако няма инструкции, връща `RuntimeError::NoInstructions`. Другите
/// грешки идват от обясненията по-горе.
///
pub fn forward(&mut self) -> Result<(), RuntimeError> {
let (new_stack, action) = self
.current_instruction()
.ok_or(RuntimeError::NoInstructions)?
.parse::<Cmd>()?
.exec_with(self.stack.clone())?;
self.instructions.pop_front();
self.stack = new_stack;
self.prev_actions.push(action);
Ok(())
}
/// Вика `.forward()` докато не свършат инструкциите (може и да се
/// имплементира по други начини, разбира се) или има грешка.
///
pub fn run(&mut self) -> Result<(), RuntimeError> {
loop {
match self.forward() {
Err(RuntimeError::NoInstructions) => return Ok(()),
Err(e) => return Err(e),
_ => (),
}
}
}
/// "Обръща" последно-изпълнената инструкция с `.forward()`. Това може да
/// се изпълнява отново и отново за всяка инструкция, изпълнена с
/// `.forward()` -- тоест, не пазим само последната инструкция, а
/// списък/стек от всичките досега.
///
/// Ако няма инструкция за връщане, очакваме
/// `RuntimeError::NoInstructions`.
///
pub fn back(&mut self) -> Result<(), RuntimeError> {
let action = self
.prev_actions
.pop()
.ok_or(RuntimeError::NoInstructions)?;
let new_stack = action.undo_on(self.stack.clone()).ok_or_else(|| {
// action undoing failed, so we return the action were it was
self.prev_actions.push(action.clone());
RuntimeError::StackUnderflow
})?;
- self.stack = new_stack;
self.instructions.push_front(action.to_instr());
+ self.stack = new_stack;
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_add_instructions_preserve_case() {
let mut interpreter = Interpreter::new();
let ins = ["PuSh 1", "pusH 2", "add"];
interpreter.add_instructions(&ins);
assert_eq!(interpreter.instructions, ins);
}
#[test]
fn test_adding_invalid_instructions_doesnt_fail() {
let mut interpreter = Interpreter::new();
let ins = ["PUSH", "PUSH 2 20", "ADD 20 200", "няма такова"];
interpreter.add_instructions(&ins);
assert_eq!(interpreter.instructions, ins);
}
#[test]
fn test_with_example() {
let mut interpreter = Interpreter::new();
let instructions = ["PUSH 0", "PUSH 42", "DIV"];
interpreter.add_instructions(&instructions);
assert_eq!(interpreter.instructions, instructions);
assert_eq!(interpreter.stack, []);
assert!(interpreter.forward().is_ok()); // PUSH 0
assert!(interpreter.forward().is_ok()); // PUSH 42
// Дотук добре:
assert_eq!(interpreter.instructions, ["DIV"]);
assert_eq!(interpreter.stack, [0, 42]);
assert_eq!(interpreter.forward(), Err(RuntimeError::DivideByZero));
+
+ assert_eq!(interpreter.instructions, ["DIV"]);
+ assert_eq!(interpreter.stack, [0, 42]);
+
// Опа, объркахме първата команда, дай назад
assert!(interpreter.back().is_ok());
assert!(interpreter.back().is_ok());
assert_eq!(interpreter.instructions, instructions);
assert_eq!(interpreter.stack, []);
if let Some(i) = interpreter.current_instruction() {
*i = String::from("PUSH 2");
}
assert!(interpreter.run().is_ok());
assert!(interpreter.instructions.is_empty());
assert_eq!(interpreter.stack, [21]);
+ }
+
+ #[test]
+ fn test_forward() {
+ let mut interpreter = Interpreter::new();
+ assert_eq!(interpreter.forward(), Err(RuntimeError::NoInstructions));
+ assert!(interpreter.instructions.is_empty());
+ assert_eq!(interpreter.stack, []);
+
+ interpreter.add_instructions(&["PUSH 7", "MUL"]);
+
+ assert_eq!(interpreter.forward(), Ok(()));
+ assert_eq!(interpreter.forward(), Err(RuntimeError::StackUnderflow));
+
+ assert_eq!(interpreter.instructions, ["MUL"]);
+ assert_eq!(interpreter.stack, [7]);
+
+ if let Some(i) = interpreter.current_instruction() {
+ *i = String::from("НЯМА");
+ }
+
+ assert_eq!(interpreter.forward(), Err(RuntimeError::InvalidCommand));
+ assert_eq!(interpreter.instructions, ["НЯМА"]);
+ assert_eq!(interpreter.stack, [7]);
+ }
+
+ #[test]
+ fn test_back() {
+ let mut interpreter = Interpreter::new();
+ interpreter.add_instructions(&["PUSH 3", "PUSH 7", "MUL"]);
+
+ assert_eq!(interpreter.back(), Err(RuntimeError::NoInstructions));
+
+ assert!(interpreter.run().is_ok());
+ assert_eq!(interpreter.instructions, VecDeque::new());
+ assert_eq!(interpreter.stack, [21]);
+
+ assert!(interpreter.back().is_ok());
+ assert_eq!(interpreter.instructions, ["MUL"]);
+ assert_eq!(interpreter.stack, [3, 7]);
+
+ if let Some(i) = interpreter.current_instruction() {
+ *i = String::from("ADD");
+ }
+
+ assert!(interpreter.run().is_ok());
+ assert_eq!(interpreter.instructions, VecDeque::new());
+ assert_eq!(interpreter.stack, [10]);
+
+ assert!(interpreter.back().is_ok());
+ assert_eq!(interpreter.instructions, ["ADD"]);
+ assert_eq!(interpreter.stack, [3, 7]);
+
+ if let Some(i) = interpreter.current_instruction() {
+ *i = String::from("SUB");
+ }
+
+ assert!(interpreter.run().is_ok());
+ assert_eq!(interpreter.instructions, VecDeque::new());
+ assert_eq!(interpreter.stack, [4]);
+
+ assert!(interpreter.back().is_ok());
+ assert_eq!(interpreter.instructions, ["SUB"]);
+ assert_eq!(interpreter.stack, [3, 7]);
+
+ if let Some(i) = interpreter.current_instruction() {
+ *i = String::from("DIV");
+ }
+
+ assert!(interpreter.run().is_ok());
+ assert_eq!(interpreter.instructions, VecDeque::new());
+ assert_eq!(interpreter.stack, [2]);
+
+ assert!(interpreter.back().is_ok());
+ assert_eq!(interpreter.instructions, ["DIV"]);
+ assert_eq!(interpreter.stack, [3, 7]);
}
}

Деян качи решение на 20.01.2021 16:50 (преди над 4 години)

//! We have some constants and 3 private types:
//! * `const *_INSTR` - those are used so as not to harcode instruction names
//! * `enum BinOp` - a binary operation, helps avoid repetition in `Cmd`
//! and `Action`
//! * `enum Cmd` - a command, the result of parsing an instruction
//! * `enum Action` - the action taken for executing a `Cmd`, holds all
//! necessary data to undo the `Cmd`
use std::{collections::VecDeque, str::FromStr};
const PUSH_INSTR: &str = "PUSH";
const POP_INSTR: &str = "POP";
const ADD_INSTR: &str = "ADD";
const MUL_INSTR: &str = "MUL";
const SUB_INSTR: &str = "SUB";
const DIV_INSTR: &str = "DIV";
#[derive(Clone, Debug)]
enum BinOp {
Add,
Mul,
Sub,
Div,
}
struct ParseBinOpError;
enum BinOpCalcError {
DivideByZero,
}
impl BinOp {
fn to_instr(&self) -> String {
match self {
BinOp::Add => ADD_INSTR,
BinOp::Mul => MUL_INSTR,
BinOp::Sub => SUB_INSTR,
BinOp::Div => DIV_INSTR,
}
.into()
}
fn calc(&self, x: i32, y: i32) -> Result<i32, BinOpCalcError> {
match self {
BinOp::Add => Ok(x + y),
BinOp::Mul => Ok(x * y),
BinOp::Sub => Ok(x - y),
BinOp::Div => {
if y == 0 {
Err(BinOpCalcError::DivideByZero)
} else {
Ok(x / y)
}
}
}
}
}
impl FromStr for BinOp {
type Err = ParseBinOpError;
fn from_str(input: &str) -> Result<Self, Self::Err> {
match input {
ADD_INSTR => Ok(BinOp::Add),
MUL_INSTR => Ok(BinOp::Mul),
SUB_INSTR => Ok(BinOp::Sub),
DIV_INSTR => Ok(BinOp::Div),
_ => Err(ParseBinOpError),
}
}
}
enum Cmd {
Push(i32),
Pop,
BinOp(BinOp),
}
struct ParseCmdError;
enum CmdExecError {
StackUnderflow,
Calc(BinOpCalcError),
}
impl From<BinOpCalcError> for CmdExecError {
fn from(e: BinOpCalcError) -> Self {
CmdExecError::Calc(e)
}
}
impl Cmd {
fn exec_with(self, mut stack: Vec<i32>) -> Result<(Vec<i32>, Action), CmdExecError> {
let mut pop_stack = || stack.pop().ok_or(CmdExecError::StackUnderflow);
let action = match self {
Cmd::Push(i) => {
stack.push(i);
Action::Push(i)
}
Cmd::Pop => {
let x = pop_stack()?;
Action::Pop(x)
}
Cmd::BinOp(op) => {
let x = pop_stack()?;
let y = pop_stack()?;
stack.push(op.calc(x, y)?);
Action::BinOp(op, x, y)
}
};
Ok((stack, action))
}
}
impl FromStr for Cmd {
type Err = ParseCmdError;
fn from_str(input: &str) -> Result<Self, Self::Err> {
// will be able to ditch the instantly-invoked closure in the future:
// https://doc.rust-lang.org/std/option/struct.NoneError.html
// https://doc.rust-lang.org/nightly/unstable-book/language-features/try-blocks.html
|| -> Option<Self> {
let mut tokens = input.split_whitespace();
let name = &*tokens.next()?.to_ascii_uppercase();
let cmd = match name {
PUSH_INSTR => Some(Cmd::Push(tokens.next()?.parse().ok()?)),
POP_INSTR => Some(Cmd::Pop),
_ => Some(Cmd::BinOp(input.parse().ok()?)),
};
if tokens.next().is_none() {
cmd
} else {
None
}
}()
.ok_or(ParseCmdError)
}
}
// The action taken for execuring a `Cmd`.
// Each variant contains the needed information to undo the corresponding `Cmd`.
#[derive(Clone, Debug)]
enum Action {
Push(i32),
Pop(i32),
BinOp(BinOp, i32, i32),
}
impl Action {
fn to_instr(&self) -> String {
match self {
Action::Push(i) => format!("{} {}", PUSH_INSTR, i),
Action::Pop(_) => POP_INSTR.into(),
Action::BinOp(op, _, _) => op.to_instr(),
}
}
// returns `None` if the stack is empty
// and the `Action` expects it not to be
fn undo_on(&self, mut stack: Vec<i32>) -> Option<Vec<i32>> {
match *self {
Action::Push(_) => {
stack.pop()?;
}
Action::Pop(x) => stack.push(x),
Action::BinOp(_, x, y) => {
stack.pop()?;
stack.push(y);
stack.push(x);
}
}
Some(stack)
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum RuntimeError {
DivideByZero,
StackUnderflow,
InvalidCommand,
NoInstructions,
}
impl From<ParseCmdError> for RuntimeError {
fn from(_: ParseCmdError) -> Self {
RuntimeError::InvalidCommand
}
}
impl From<CmdExecError> for RuntimeError {
fn from(err: CmdExecError) -> Self {
match err {
CmdExecError::Calc(BinOpCalcError::DivideByZero) => RuntimeError::DivideByZero,
CmdExecError::StackUnderflow => RuntimeError::StackUnderflow,
}
}
}
#[derive(Debug, Default)]
pub struct Interpreter {
pub instructions: VecDeque<String>,
pub stack: Vec<i32>,
prev_actions: Vec<Action>,
}
impl Interpreter {
/// Конструира нов интерпретатор с празен стек и никакви инструкции.
///
/// ```
/// use solution::Interpreter;
/// use std::collections::VecDeque;
///
/// let interpreter = Interpreter::new();
/// assert_eq!(interpreter.instructions, VecDeque::new());
/// assert_eq!(interpreter.stack, vec![]);
/// ```
pub fn new() -> Self {
Self {
instructions: VecDeque::new(),
stack: vec![],
prev_actions: vec![],
}
}
/// Добавя инструкции от дадения списък към края на `instructions`.
/// Инструкциите не се интерпретират, само се записват.
/// Пример:
///
/// ```
/// use solution::Interpreter;
///
/// let mut interpreter = Interpreter::new();
/// let ins = [
/// "PUSH 1",
/// "PUSH 2",
/// "ADD",
/// ];
///
/// interpreter.add_instructions(&ins);
///
/// assert_eq!(interpreter.instructions, ins);
/// assert_eq!(interpreter.stack, vec![]);
/// ```
pub fn add_instructions(&mut self, instructions: &[&str]) {
self.instructions
.extend(instructions.iter().map(|&s| s.into()));
}
/// Връща mutable reference към инструкцията, която ще се изпълни при
/// следващия `.forward()` -- първата в списъка/дека.
///
/// ```
/// use solution::Interpreter;
///
/// let mut interpreter = Interpreter::new();
/// assert_eq!(interpreter.current_instruction(), None);
///
/// let ins = [
/// "PUSH 1",
/// "PUSH 2",
/// "ADD",
/// ];
/// interpreter.add_instructions(&ins);
///
/// assert_eq!(interpreter.current_instruction(), Some(&mut String::from("PUSH 1")));
/// ```
pub fn current_instruction(&mut self) -> Option<&mut String> {
self.instructions.front_mut()
}
/// Интерпретира първата инструкция в `self.instructions` по правилата
/// описани по-горе. Записва някаква информация за да може успешно да се
/// изпълни `.back()` в по-нататъшен момент.
///
/// Ако няма инструкции, връща `RuntimeError::NoInstructions`. Другите
/// грешки идват от обясненията по-горе.
///
pub fn forward(&mut self) -> Result<(), RuntimeError> {
let (new_stack, action) = self
.current_instruction()
.ok_or(RuntimeError::NoInstructions)?
.parse::<Cmd>()?
.exec_with(self.stack.clone())?;
self.instructions.pop_front();
self.stack = new_stack;
self.prev_actions.push(action);
Ok(())
}
/// Вика `.forward()` докато не свършат инструкциите (може и да се
/// имплементира по други начини, разбира се) или има грешка.
///
pub fn run(&mut self) -> Result<(), RuntimeError> {
loop {
match self.forward() {
Err(RuntimeError::NoInstructions) => return Ok(()),
Err(e) => return Err(e),
_ => (),
}
}
}
/// "Обръща" последно-изпълнената инструкция с `.forward()`. Това може да
/// се изпълнява отново и отново за всяка инструкция, изпълнена с
/// `.forward()` -- тоест, не пазим само последната инструкция, а
/// списък/стек от всичките досега.
///
/// Ако няма инструкция за връщане, очакваме
/// `RuntimeError::NoInstructions`.
///
pub fn back(&mut self) -> Result<(), RuntimeError> {
let action = self
.prev_actions
.pop()
.ok_or(RuntimeError::NoInstructions)?;
let new_stack = action.undo_on(self.stack.clone()).ok_or_else(|| {
// action undoing failed, so we return the action were it was
self.prev_actions.push(action.clone());
RuntimeError::StackUnderflow
})?;
self.instructions.push_front(action.to_instr());
self.stack = new_stack;
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_add_instructions_preserve_case() {
let mut interpreter = Interpreter::new();
let ins = ["PuSh 1", "pusH 2", "add"];
interpreter.add_instructions(&ins);
assert_eq!(interpreter.instructions, ins);
}
#[test]
fn test_adding_invalid_instructions_doesnt_fail() {
let mut interpreter = Interpreter::new();
let ins = ["PUSH", "PUSH 2 20", "ADD 20 200", "няма такова"];
interpreter.add_instructions(&ins);
assert_eq!(interpreter.instructions, ins);
}
#[test]
fn test_with_example() {
let mut interpreter = Interpreter::new();
let instructions = ["PUSH 0", "PUSH 42", "DIV"];
interpreter.add_instructions(&instructions);
assert_eq!(interpreter.instructions, instructions);
assert_eq!(interpreter.stack, []);
assert!(interpreter.forward().is_ok()); // PUSH 0
assert!(interpreter.forward().is_ok()); // PUSH 42
// Дотук добре:
assert_eq!(interpreter.instructions, ["DIV"]);
assert_eq!(interpreter.stack, [0, 42]);
assert_eq!(interpreter.forward(), Err(RuntimeError::DivideByZero));
assert_eq!(interpreter.instructions, ["DIV"]);
assert_eq!(interpreter.stack, [0, 42]);
// Опа, объркахме първата команда, дай назад
assert!(interpreter.back().is_ok());
assert!(interpreter.back().is_ok());
assert_eq!(interpreter.instructions, instructions);
assert_eq!(interpreter.stack, []);
if let Some(i) = interpreter.current_instruction() {
*i = String::from("PUSH 2");
}
assert!(interpreter.run().is_ok());
assert!(interpreter.instructions.is_empty());
assert_eq!(interpreter.stack, [21]);
}
#[test]
fn test_forward() {
let mut interpreter = Interpreter::new();
assert_eq!(interpreter.forward(), Err(RuntimeError::NoInstructions));
assert!(interpreter.instructions.is_empty());
assert_eq!(interpreter.stack, []);
interpreter.add_instructions(&["PUSH 7", "MUL"]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Err(RuntimeError::StackUnderflow));
assert_eq!(interpreter.instructions, ["MUL"]);
assert_eq!(interpreter.stack, [7]);
if let Some(i) = interpreter.current_instruction() {
*i = String::from("НЯМА");
}
assert_eq!(interpreter.forward(), Err(RuntimeError::InvalidCommand));
assert_eq!(interpreter.instructions, ["НЯМА"]);
assert_eq!(interpreter.stack, [7]);
}
#[test]
fn test_back() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&["PUSH 3", "PUSH 7", "MUL"]);
assert_eq!(interpreter.back(), Err(RuntimeError::NoInstructions));
assert!(interpreter.run().is_ok());
assert_eq!(interpreter.instructions, VecDeque::new());
assert_eq!(interpreter.stack, [21]);
assert!(interpreter.back().is_ok());
assert_eq!(interpreter.instructions, ["MUL"]);
assert_eq!(interpreter.stack, [3, 7]);
- if let Some(i) = interpreter.current_instruction() {
- *i = String::from("ADD");
- }
+ let mut check = |instr: &str, out| {
+ if let Some(i) = interpreter.current_instruction() {
+ *i = String::from(instr);
+ }
- assert!(interpreter.run().is_ok());
- assert_eq!(interpreter.instructions, VecDeque::new());
- assert_eq!(interpreter.stack, [10]);
+ assert!(interpreter.run().is_ok());
+ assert_eq!(interpreter.instructions, VecDeque::new());
+ assert_eq!(interpreter.stack, [out]);
- assert!(interpreter.back().is_ok());
- assert_eq!(interpreter.instructions, ["ADD"]);
- assert_eq!(interpreter.stack, [3, 7]);
+ assert!(interpreter.back().is_ok());
+ assert_eq!(interpreter.instructions, [instr]);
+ assert_eq!(interpreter.stack, [3, 7]);
+ };
- if let Some(i) = interpreter.current_instruction() {
- *i = String::from("SUB");
- }
-
- assert!(interpreter.run().is_ok());
- assert_eq!(interpreter.instructions, VecDeque::new());
- assert_eq!(interpreter.stack, [4]);
-
- assert!(interpreter.back().is_ok());
- assert_eq!(interpreter.instructions, ["SUB"]);
- assert_eq!(interpreter.stack, [3, 7]);
-
- if let Some(i) = interpreter.current_instruction() {
- *i = String::from("DIV");
- }
-
- assert!(interpreter.run().is_ok());
- assert_eq!(interpreter.instructions, VecDeque::new());
- assert_eq!(interpreter.stack, [2]);
-
- assert!(interpreter.back().is_ok());
- assert_eq!(interpreter.instructions, ["DIV"]);
- assert_eq!(interpreter.stack, [3, 7]);
+ check("ADD", 10);
+ check("SUB", 4);
+ check("DIV", 2);
}
}