Как проверить введенное римское число на правильную запись?

Question

[pipetto]

Пытаюсь сделать проверку римского числа. Конкретно проблема возникла при рассмотрении того случая, что пользователь вводит меньшее число перед большим. Такое число программа при переводе в арабское, будет складывать цифры. Например "DM", "LXC" , "CDCM"...

#include <iostream>
#include <string>

using namespace std;

const int size_num = 13;
char Roman_nums[][3] = { "I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M" };
int num[] = { 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000 };

bool isValidRomanNumeral(string roman) {
	for (int i = 0; i < roman.length(); i++) {//Проверка на использование допустимых символов
		int check = 0;
		for (int j = 0; j < size_num; j += 2) {
			if (roman.substr(i, 1) == Roman_nums[j]){
				check++;
				break;
			}
		}
		if (check == 0)
			return false;
	}
	
	for (int i = 11; i > 0; i -= 2) {//Проверка на отсутствие повторяющихся чисел размерностью 2
		int counter = 0;
		for (int j = 0; j < roman.length(); j++) {
			if (roman.substr(j, 2) == Roman_nums[i]) {
				++counter;
				if (counter > 1)
					return false;
			}
		}
	}

	for (int i = 12; i >= 0; i -= 2) {//Проверка на отсутствие повтора больше 3х раз подряд чисел 
		int counter = 0;
		for (int j = 1; j < roman.length(); j++) {
			if (roman.substr(j, 1) == Roman_nums[i] && roman.substr(j - 1, 1) == Roman_nums[i]) {
				++counter;
				if (counter > 3)
					return false;
			}
		}
	}

	return true;
}

int main() {
	string number;

	do {
		cout << "Enter the Rom number\n";
		cin >> number;
	} while (isValidRomanNumeral(number) == false);

	return 0;

Answer 1

[Rsa97]

Лень вспоминать C, держите вариант конечного автомата проверки римских цифр на JS.

// Матрица переходов конечного автомата
// -1 - допустимое конечное состояние
// null - недопустимое состояние
const dka = [
  [-1, 1, 5, 4, 10, 9, 15, 14], // 0
  [-1, 2, 5, 4, 10, 9, 15, 14], // 1
  [-1, 3, 5, 4, 10, 9, 15, 14], // 2
  [-1, null, 5, 4, 10, 9, 15, 14], // 3
  [-1, 8, 8, 7, null, null, null, null], // 4
  [-1, null, null, 6, 10, 9, 15, 14], // 5
  [-1, null, null, 7, 10, 9, 15, 14], // 6
  [-1, null, null, 8, 10, 9, 15, 14], // 7
  [-1, null, null, null, 10, 9, 15, 14], // 8
  [-1, null, null, 13, 13, 12, null, null], // 9
  [-1, null, null, null, null, 11, 15, 14], // 10
  [-1, null, null, null, null, 12, 15, 14], // 11
  [-1, null, null, null, null, 13, 15, 14], // 12
  [-1, null, null, null, null, null, 15, 14], // 13
  [-1, null, null, null, null, 18, 18, 17], // 14
  [-1, null, null, null, null, null, null, 16], // 15
  [-1, null, null, null, null, null, null, 17], // 16
  [-1, null, null, null, null, null, null, 18], // 17
  [-1, null, null, null, null, null, null, null], // 18
];

// Алфавит
const alphabet = 'MDCLXVI';

// Разбивает строку на лексемы
// (номера символов в алфавите, начиная с 1)
// для отсутствующих символов возвращает 0
const lexer = (str) => str.split('').map((l) => alphabet.indexOf(l) + 1);

// Проверяет корректность числа в римской записи
const check = (str) => {
  const lexems = lexer(str);
  let state = 0;
  let idx = 0;
  while (true) {
    const lex = lexems[idx] ?? 0;
    state = dka[state][lex];
    if (state === null) {
      return false;
    }
    if (state === -1) {
      return  idx === str.length;
    }
    idx += 1;
  }
}

Comments

[Wataru]

Интересно, откуда этот автомат взялся. Не регулярка ли лежит в его основе?

[Rsa97]

Wataru, Регулярка.

M{0,3}(?:CM|CD|D?C{0,3})(?:XC|XL|L?X{0,3})(?:IX|IV|V?I{0,3})

А дальше преобразование в синтаксическую диаграмму, КА и приведение к ДКА.

Answer 2

[dollar]

Просто сделайте функцию перевода римского числа в обычное (int32). Ошибка (т.е. исключение) в ходе работы этой функции и будет означать невозможность преобразования. Алгоритм тот же.

Другими словами, используйте алгоритм перевода римских в арабские. Какие-то новые идеи не нужны, так как алгоритм известен (а если нет, то гугл в помощь). Проблемы нет. Нужно лишь перевести алгоритм на язык программирования. Задача для джуна. К слову, наверняка реализации уже есть для разных ЯП, и нужно лишь правильно загуглить.

Comments

[pipetto]

Программа написана, но такие случаи рассматриваются именно как сложение, ошибки не возникает. Задача стояла в написании простой программки без использования строк и map-ов