Преобразовать целые числа в римские цифры с помощью схемы перевода, ориентированной на синтаксис?
Книга Дракона включает в себя упражнение по преобразованию целых чисел в римские числа с использованием схемы перевода, ориентированной на синтаксис.
Как это можно сделать?
Да, я знаю ... Хотел бы я доказать, что не обманываю. На самом деле это вопрос домашнего задания для студентов CS ... Просто, не для меня, я просто читаю книгу самостоятельно, и у меня нет учителя (или достаточно знающего друга), чтобы спросить.
Ответы 3
Я бы рассмотрел парсинг справа налево.
Сначала я сопоставлю столбец единиц:
0 -> ''
1 -> 'I'
2 -> 'II'
3 -> 'III'
4 -> 'IV'
...
9 -> 'IX'
Затем, если бы был второй столбец (например, второй справа столбец = десятки), я бы использовал его для сопоставления с
0 -> ''
1 -> 'X'
2 -> 'XX'
...
9 -> 'XC'
Это нужно будет добавить к исходному выводу.
Повторите для следующих столбцов (сотни, тысячи), пока у вас не закончатся буквы.
Еще раз проверьте, не является ли число "0" или отрицательным.
Это означает, что для создания контекстно-свободной грамматики, которая затем позволила бы мне преобразовать с использованием схемы перевода, ориентированной на sytanx, мне нужно создать 10 правил для каждого «столбца». (итак, около 34 правил, чтобы добраться до 3999) Я прав?
Я действительно думал о чем-то подобном, я ожидал, что будет более элегантный метод ... Есть ли?
Да, это означает 10 правил на столбец. Я думаю, вы могли бы написать одну функцию, которая работает для каждого из столбцов и принимает буквы в качестве параметров ... Итак, для 219 вы должны вывести f (2, 'C', 'D', 'M') + f (1. 'X', 'L', 'C') + f (9, 'I', 'V', 'X'), однако, не "чувствует себя" контекстно-зависимым.
Это неправильный ответ, потому что здесь нет грамматики. Никакой функции не должно быть. Перевод должен давать результат во время обхода дерева, и его невозможно определить, насколько глубоко вы находитесь в дереве.
Другой способ - сохранить в двумерном массиве римские цифры для 1, 5, 10, 50, 100, 500, 1000 и так далее. Пример (в массиве PHP):
$roman = array(
[0] = array( 1=>"I", 5=>"V", 10=>"X" ),
[1] = array( 1=>"X", 5=>"L", 10=>"C" ),
[2] = array( 1=>"C", 5=>"D", 10=>"M" ),
[3] = array( 1=>"M", 5=>"^V", 10=>"^X" ),
);
Затем возьмите каждую цифру справа налево и примените следующий перевод. Установите переменную $ level = 0 и увеличивайте ее значение на 1 после обработки каждой цифры:
1 => $roman[$level][1]
2 => $roman[$level][1].$roman[$level][1]
3 => $roman[$level][1].$roman[$level][1].$roman[$level][1]
4 => $roman[$level][1].$roman[$level][5]
5 => $roman[$level][5]
6 => $roman[$level][5].$roman[$level][1]
7 => $roman[$level][5].$roman[$level][1].$roman[$level][1]
8 => $roman[$level][5].$roman[$level][1].$roman[$level][1].$roman[$level][1]
9 => $roman[$level][1].$roman[$level][10]
(в PHP '.' объединяет две строки)
Пример: 1945 г.
5 => $roman[0][5] = "V"
4 => $roman[1][1].$roman[1][5] = "XL"
9 => $roman[2][1].$roman[2][10] = "CM"
1 => $roman[3][1] = "M"
Итак, переведенное число - "MCMXLV".
Извините, это может не полностью ответить на ваш вопрос, но я надеюсь, что это поможет в любом случае ..
Далее идет грамматика для представления синтаксически управляемого перевода числа в формате 1xxx в римские цифры.
число = Одна тысяча цифр3 цифра2 цифра1 | nzdigit3 digit2 digit1 | nzdigit2 digit1 | nzdigit1
OneThousand -> 1 {print('M')}
digit3 -> 0 digit3 -> nzdigit3
nzdigit3 -> 1 print('C') nzdigit3 -> 2 print('CC') nzdigit3 -> 3 print('CCC') nzdigit3 -> 4 print('CCCC') nzdigit3 -> 5 print('D') nzdigit3 -> 6 print('DC') nzdigit3 -> 7 print('DCC') nzdigit3 -> 8 print('DCCC') nzdigit3 -> 9 print('DCCCc')
Аналогичным образом напишите определение цифр в позиции 2 и 1, и вам потребуется перевод.
похоже на вопрос домашнего задания, пахнет вопросом домашнего задания ... ;-)