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

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

Решение на Reversible Interpreter от Тервел Вълков

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

Към профила на Тервел Вълков

Резултати

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

Код

use std::collections::VecDeque;
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum RuntimeError {
DivideByZero,
StackUnderflow,
InvalidCommand,
NoInstructions,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum ArithmeticOperation {
Add,
Mul,
Sub,
Div,
}
#[derive(Debug, PartialEq, Eq)]
enum Command {
Push(i32),
Pop,
Arithmetic(ArithmeticOperation),
}
impl Command {
fn read(instruction: &str) -> Result<Self, RuntimeError> {
let instruction_elements: Vec<&str> = instruction.split_whitespace().collect();
if instruction_elements.is_empty() {
return Err(RuntimeError::InvalidCommand);
}
if instruction_elements.len() == 1 {
match instruction_elements[0] {
"POP" => return Ok(Self::Pop),
"ADD" => return Ok(Self::Arithmetic(ArithmeticOperation::Add)),
"MUL" => return Ok(Self::Arithmetic(ArithmeticOperation::Mul)),
"SUB" => return Ok(Self::Arithmetic(ArithmeticOperation::Sub)),
"DIV" => return Ok(Self::Arithmetic(ArithmeticOperation::Div)),
_ => return Err(RuntimeError::InvalidCommand),
}
}
if instruction_elements.len() == 2 {
if instruction_elements[0] == "PUSH" {
match instruction_elements[1].parse::<i32>() {
Err(_) => return Err(RuntimeError::InvalidCommand),
Ok(value) => return Ok(Self::Push(value)),
}
}
}
Err(RuntimeError::InvalidCommand)
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
enum ExecutedCommand {
Push(i32),
Pop(i32),
Arithmetic(ArithmeticOperation, i32, i32),
}
#[derive(Debug, Default)]
pub struct Interpreter {
pub instructions: VecDeque<String>,
pub stack: Vec<i32>,
// + още полета за поддръжка на .back() метода
executed_instructions: VecDeque<ExecutedCommand>,
}
impl Interpreter {
pub fn new() -> Self {
return Interpreter {
instructions: VecDeque::new(),
stack: Vec::new(),
executed_instructions: VecDeque::new(),
}
}
pub fn add_instructions(&mut self, instructions: &[&str]) {
for instruction in instructions {
let instruction = instruction.trim().to_uppercase().to_string();
self.instructions.push_back(instruction);
}
}
pub fn current_instruction(&mut self) -> Option<&mut String> {
self.instructions.front_mut()
}
fn pop(&mut self) -> Result<i32, RuntimeError> {
match self.stack.pop() {
None => Err(RuntimeError::StackUnderflow),
Some(value) => Ok(value),
}
}
fn pop_two(&mut self) -> Result<(i32, i32), RuntimeError> {
let top = self.pop()?;
let next = self.pop()?;
Ok((top, next))
}
fn push(&mut self, value: i32) {
self.stack.push(value);
}
pub fn forward(&mut self) -> Result<(), RuntimeError> {
match self.current_instruction() {
None => Err(RuntimeError::NoInstructions),
Some(instruction) => {
let command = Command::read(instruction)?;
match command {
Command::Push(value) => {
self.push(value);
self.executed_instructions.push_back(ExecutedCommand::Push(value))
}
Command::Pop => {
let popped = self.pop()?;
self.executed_instructions.push_back(ExecutedCommand::Pop(popped));
}
Command::Arithmetic(arithmetic_command) => {
let (top, next) = self.pop_two()?;
match arithmetic_command {
ArithmeticOperation::Add => self.push(top + next),
ArithmeticOperation::Mul => self.push(top * next),
ArithmeticOperation::Sub => self.push(top - next),
ArithmeticOperation::Div => {
if next == 0 {
self.push(next);
self.push(top);
return Err(RuntimeError::DivideByZero);
}
self.push(top / next)
}
}
self.executed_instructions.push_back(ExecutedCommand::Arithmetic(arithmetic_command, top, next));
}
}
self.instructions.pop_front();
Ok(())
}
}
}
pub fn run(&mut self) -> Result<(), RuntimeError> {
loop {
match self.forward() {
Err(RuntimeError::NoInstructions) => return Ok(()),
Err(e) => return Err(e),
_ => (),
}
}
}
pub fn back(&mut self) -> Result<(), RuntimeError> {
match self.executed_instructions.back() {
None => return Err(RuntimeError::NoInstructions),
Some(executed_command) => {
match executed_command.clone() {
ExecutedCommand::Push(value) => {
let _ = self.pop()?;
self.instructions.push_front("PUSH ".to_string() + &value.to_string());
},
ExecutedCommand::Pop(popped) => {
self.push(popped);
self.instructions.push_front("POP".to_string());
},
ExecutedCommand::Arithmetic(command, top, next) => {
let _ = self.pop()?;
self.push(next);
self.push(top);
match command {
ArithmeticOperation::Add => self.instructions.push_front("ADD".to_string()),
ArithmeticOperation::Mul => self.instructions.push_front("MUL".to_string()),
ArithmeticOperation::Sub => self.instructions.push_front("SUB".to_string()),
ArithmeticOperation::Div => self.instructions.push_front("DIV".to_string())
}
}
};
self.executed_instructions.pop_back();
Ok(())
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn enum_command_push_test() {
assert_eq!(Command::read("PUSH 1"), Ok(Command::Push(1)));
assert_eq!(Command::read("PUSH 1"), Ok(Command::Push(1)));
assert_eq!(Command::read("PUSH 123"), Ok(Command::Push(123)));
assert_eq!(Command::read("PUSH -1"), Ok(Command::Push(-1)));
assert_eq!(Command::read("PUSH"), Err(RuntimeError::InvalidCommand));
assert_eq!(Command::read("PUSH 1 2"), Err(RuntimeError::InvalidCommand));
}
#[test]
fn enum_command_pop_test() {
assert_eq!(Command::read("POP"), Ok(Command::Pop));
assert_eq!(Command::read("POP 1"), Err(RuntimeError::InvalidCommand));
assert_eq!(Command::read("POP 1 2"), Err(RuntimeError::InvalidCommand));
assert_eq!(Command::read("SOME_OTHER_COMMAND"), Err(RuntimeError::InvalidCommand));
}
#[test]
fn enum_command_arithmetic_test() {
assert_eq!(Command::read("ADD"), Ok(Command::Arithmetic(ArithmeticOperation::Add)));
assert_eq!(Command::read("MUL"), Ok(Command::Arithmetic(ArithmeticOperation::Mul)));
assert_eq!(Command::read("SUB"), Ok(Command::Arithmetic(ArithmeticOperation::Sub)));
assert_eq!(Command::read("DIV"), Ok(Command::Arithmetic(ArithmeticOperation::Div)));
assert_eq!(Command::read("SQR"), Err(RuntimeError::InvalidCommand));
assert_eq!(Command::read("Add"), Err(RuntimeError::InvalidCommand));
assert_eq!(Command::read("ADD 1"), Err(RuntimeError::InvalidCommand));
assert_eq!(Command::read("ADD 1 2"), Err(RuntimeError::InvalidCommand));
}
#[test]
fn add_instructions_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"PUSH 2",
"ADD",
" pUsH 1 ",
" push 2",
" AdD ",
" NOARGUMENTPUSH ",
]);
assert_eq!(interpreter.instructions.len(), 7);
assert_eq!(interpreter.instructions[0], "PUSH 1");
assert_eq!(interpreter.instructions[1], "PUSH 2");
assert_eq!(interpreter.instructions[2], "ADD");
assert_eq!(interpreter.instructions[3], "PUSH 1");
assert_eq!(interpreter.instructions[4], "PUSH 2");
assert_eq!(interpreter.instructions[5], "ADD");
assert_eq!(interpreter.instructions[6], "NOARGUMENTPUSH");
}
#[test]
fn add_instructions_multiple_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"PUSH 2",
]);
assert_eq!(interpreter.instructions.len(), 2);
interpreter.add_instructions(&[
"ADD",
" pUsH 1 ",
" push 2",
]);
assert_eq!(interpreter.instructions.len(), 5);
interpreter.add_instructions(&[
" AdD ",
" NOARGUMENTPUSH ",
]);
assert_eq!(interpreter.instructions.len(), 7);
assert_eq!(interpreter.instructions[0], "PUSH 1");
assert_eq!(interpreter.instructions[1], "PUSH 2");
assert_eq!(interpreter.instructions[2], "ADD");
assert_eq!(interpreter.instructions[3], "PUSH 1");
assert_eq!(interpreter.instructions[4], "PUSH 2");
assert_eq!(interpreter.instructions[5], "ADD");
assert_eq!(interpreter.instructions[6], "NOARGUMENTPUSH");
}
#[test]
fn current_instruction_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"PUSH 2",
]);
let result = &mut "PUSH 1".to_string();
assert_eq!(interpreter.current_instruction(), Some(result));
}
#[test]
fn push_test() {
let mut interpreter = Interpreter::new();
interpreter.push(1);
interpreter.push(2);
interpreter.push(3);
assert_eq!(interpreter.stack, vec![1,2,3]);
}
#[test]
fn pop_test() {
let mut interpreter = Interpreter::new();
interpreter.stack = vec![1, 2, 3];
assert_eq!(interpreter.pop(), Ok(3));
assert_eq!(interpreter.pop(), Ok(2));
assert_eq!(interpreter.pop(), Ok(1));
assert_eq!(interpreter.pop(), Err(RuntimeError::StackUnderflow));
}
#[test]
fn pop_two_test() {
let mut interpreter = Interpreter::new();
interpreter.stack = vec![1, 2, 3, 4];
assert_eq!(interpreter.pop_two(), Ok((4, 3)));
assert_eq!(interpreter.pop_two(), Ok((2, 1)));
assert_eq!(interpreter.pop(), Err(RuntimeError::StackUnderflow));
interpreter.stack = vec![0, 1, 2];
assert_eq!(interpreter.pop_two(), Ok((2, 1)));
assert_eq!(interpreter.pop_two(), Err(RuntimeError::StackUnderflow));
}
#[test]
fn forward_simple_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"PUSH 2",
"ADD",
"POP",
]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.stack, vec![1, 2]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.stack, vec![3]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.stack, vec![]);
}
#[test]
fn forward_expression_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"PUSH 2",
"ADD",
"PUSH 3",
"ADD",
"PUSH 4",
"MUL",
"PUSH 5",
"SUB",
"PUSH 19",
"DIV",
"PUSH 6",
"PUSH 18",
"DIV",
"POP",
"POP",
]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.stack, vec![3]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.stack, vec![3, 3]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.stack, vec![6]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.stack, vec![6, 4]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.stack, vec![24]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.stack, vec![24, 5]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.stack, vec![-19]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.stack, vec![-19, 19]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.stack, vec![-1]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.stack, vec![-1, 6, 18]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.stack, vec![-1, 3]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.stack, vec![]);
}
#[test]
fn forward_add_to_executed_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"PUSH 2",
"ADD",
"POP",
]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.executed_instructions, vec![ExecutedCommand::Push(1),
ExecutedCommand::Push(2),
ExecutedCommand::Arithmetic(ArithmeticOperation::Add, 2, 1),
ExecutedCommand::Pop(3)]);
}
#[test]
fn forward_add_to_executed_test_with_error_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"ADD",
"POP",
]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Err(RuntimeError::StackUnderflow));
assert_eq!(interpreter.forward(), Err(RuntimeError::StackUnderflow));
assert_eq!(interpreter.forward(), Err(RuntimeError::StackUnderflow));
assert_eq!(interpreter.executed_instructions, vec![ExecutedCommand::Push(1)]);
}
#[test]
fn forward_error_no_instructions_test() {
let mut interpreter = Interpreter::new();
assert_eq!(interpreter.forward(), Err(RuntimeError::NoInstructions));
}
#[test]
fn forward_error_pop_arg_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"POP 1",
"PUSH 2",
]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Err(RuntimeError::InvalidCommand));
assert_eq!(interpreter.forward(), Err(RuntimeError::InvalidCommand)); // we are still on "POP 1"
}
#[test]
fn forward_error_pop_empty_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"POP",
"POP",
]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Err(RuntimeError::StackUnderflow));
}
#[test]
fn forward_error_zero_division_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 0",
"PUSH 2",
"DIV",
]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.stack, vec![0, 2]);
assert_eq!(interpreter.forward(), Err(RuntimeError::DivideByZero));
assert_eq!(interpreter.stack, vec![0, 2]);
}
#[test]
fn run_simple_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"PUSH 2",
"ADD"
]);
assert_eq!(interpreter.run(), Ok(()));
assert_eq!(interpreter.stack, vec![3]);
assert!(interpreter.instructions.is_empty());
}
#[test]
fn run_pop_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"PUSH 2",
"ADD",
"POP"
]);
assert_eq!(interpreter.run(), Ok(()));
assert!(interpreter.stack.is_empty());
assert!(interpreter.instructions.is_empty());
}
#[test]
fn run_expression_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"PUSH 2",
"ADD",
"PUSH 9",
"SUB",
"PUSH 4",
"PUSH 5",
"MUL",
"SUB"
]);
assert_eq!(interpreter.run(), Ok(()));
assert_eq!(interpreter.stack, vec![14]);
assert!(interpreter.instructions.is_empty());
}
#[test]
fn run_error_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 0",
"PUSH 2",
"DIV"
]);
assert_eq!(interpreter.run(), Err(RuntimeError::DivideByZero));
assert_eq!(interpreter.stack, vec![0, 2]);
assert_eq!(interpreter.instructions, vec!["DIV"]);
}
#[test]
fn back_push_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"PUSH 2",
]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.stack, vec![1, 2]);
assert!(interpreter.instructions.is_empty());
assert_eq!(interpreter.back(), Ok(()));
assert_eq!(interpreter.stack, vec![1]);
assert_eq!(interpreter.instructions, vec!["PUSH 2"]);
assert_eq!(interpreter.back(), Ok(()));
assert!(interpreter.stack.is_empty());
assert_eq!(interpreter.instructions, vec!["PUSH 1", "PUSH 2"]);
}
#[test]
fn back_pop_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"POP",
]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Ok(()));
assert!(interpreter.stack.is_empty());
assert!(interpreter.instructions.is_empty());
assert_eq!(interpreter.back(), Ok(()));
assert_eq!(interpreter.stack, vec![1]);
assert_eq!(interpreter.instructions, vec!["POP"]);
}
#[test]
fn back_arithmetic_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"PUSH 2",
"ADD",
]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.stack, vec![3]);
assert!(interpreter.instructions.is_empty());
assert_eq!(interpreter.back(), Ok(()));
assert_eq!(interpreter.stack, vec![1, 2]);
assert_eq!(interpreter.instructions, vec!["ADD"]);
}
#[test]
fn back_division_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 0",
"PUSH 4",
"DIV",
]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.forward(), Err(RuntimeError::DivideByZero));
assert_eq!(interpreter.stack, vec![0, 4]);
assert_eq!(interpreter.instructions, vec!["DIV"]);
assert_eq!(interpreter.back(), Ok(()));
assert_eq!(interpreter.stack, vec![0]);
assert_eq!(interpreter.instructions, vec!["PUSH 4", "DIV"]);
assert_eq!(interpreter.back(), Ok(()));
assert!(interpreter.stack.is_empty());
assert_eq!(interpreter.instructions, vec!["PUSH 0", "PUSH 4", "DIV"]);
interpreter.current_instruction().map(|i| *i = String::from("PUSH 2"));
assert_eq!(interpreter.run(), Ok(()));
assert_eq!(interpreter.stack, vec![2]);
assert!(interpreter.instructions.is_empty());
}
#[test]
fn back_error_test() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 0",
]);
assert_eq!(interpreter.forward(), Ok(()));
assert_eq!(interpreter.back(), Ok(()));
assert_eq!(interpreter.back(), Err(RuntimeError::NoInstructions));
}
}

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

Compiling solution v0.1.0 (/tmp/d20210120-1538662-1qbdot4/solution)
    Finished test [unoptimized + debuginfo] target(s) in 2.84s
     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

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

Тервел качи първо решение на 14.01.2021 16:41 (преди над 4 години)