Страницы

Перевод текстовой формы числа в машинную

Математическое определения значения числа, записанного в позиционной системе счисления:

$$ Ч = \sum_{р=0}^{к} Ц_р·О^{р} $$
Ч— значение числа
р— разряд цифры
к— конечный, старший разряд в числе
$$ Ц_р $$— Значение цифры в соответствующем разряде
О— основание системы счисления (10)

Если считать не по разряду цифр, а их положению в тексте начиная слева, то с учётом того, что в традиционной записи старшие разряды записывают раньше младших, формула примет вид:

$$ Ч = \sum_{п=0}^{к} Ц_р·О^{к-п} $$

От прямого использования возведения в степень можно избавиться с помощью эквивалентной рекурентной формулы:

$$ З_0 = Ц_0 $$ $$ З_п = Ц_{п-1}·О + Ц_п $$ $$ Ч = З_к $$

В коде разбора текстового представления числа, естественно, нужно учитывать возможность неправильного ввода, как и возможность переполнения целевого диапазона. Черновую версию алгоритма можно записать так:

Получи начальную литеру; IF текущая литера не цифра THEN ошибка - не число на входе ELSE
val := численное значение цифры; Следующая литера; WHILE литера является цифрой & цифру можно включить в значение без переполнения DO Присоедини к val численное значение цифры; Следующая литера END;
IF текущая литера является цифрой THEN ошибка - переполнение целевого диапазона, число в строке слишком большое END END

Код

Для 10-ричной системы счисления
CONST Radix = 10;
  
PROCEDURE ValDigit(c: CHAR; VAR val: INTEGER): BOOLEAN;
BEGIN
 IF ("0" <= c) & (c <= "9") THEN
   val := ORD(c) - ORD("0")
 ELSE
   val := -1
 END
RETURN
 val >= 0
END ValDigit;
Для 16-ричной системы счисления
CONST Radix = 10H;
  
PROCEDURE ValDigit(c: CHAR; VAR val: INTEGER): BOOLEAN;
BEGIN
 IF ("0" <= c) & (c <= "9") THEN
   val := ORD(c) - ORD("0")
 ELSIF ("A" <= c) & (c <= "F") THEN
   val := 10 + ORD(c) - ORD("A")
 ELSEкорр
   val := -1
 END
RETURN
 val >= 0
END ValDigit;
PROCEDURE Parse(s: ARRAY OF CHAR; VAR i: INTEGER;
                VAR val: INTEGER): INTEGER;
VAR d, mark: INTEGER;
BEGIN
 IF ValDigit(s[i], val) THEN
   INC(i);
   WHILE ValDigit(s[i], d) & (val <= (Max - d) DIV Radix) DO
     val := val * Radix + d;
     INC(i)
   END;
   IF ValDigit(s[i], d) THEN mark := ErrTooLarge ELSE mark := Ok END
 ELSE mark := ErrNoDigits
 END
RETURN mark
END Parse

Проверка возможного переполнения строится на сравнении с границей, полученной обратными вычислениями от верхней границы INTEGER.

    val <= (Max - d) DIV Radix

Она проста, но довольно ресурсоёмка, особенно учитывая, что количество вместимых цифр известно, и только последняя из них может привести к переполнению. Следующая двухуровненвая проверка позволяет в большинстве случаев обойтись одним сравнением с константой.

   (val < Max DIV Radix)
OR (val = Max DIV Radix) & (d <= Max MOD Radix)

Так как алгоритм не допускает переполнения при вычислениях, он подходит для языков программирования, в которых арифметическое переполнение является прямой ошибкой или его поведение не определено.

При разборе числа со знаком нужно учитывать, что в большинстве языков программирования используют весь диапазон вместимых чисел, а в ставшей стандартной системе дополнительного кода для кодирования отрицательных чисел, Min = -Max - 1. Чтобы не учитывать это особое значение при проверке на переполнение, можно производить вычисления сразу в более ёмком отрицательном диапазоне, а для положительных чисел поправлять значение в конце.

PROCEDURE InRange(pre, digit: INTEGER): BOOLEAN; CONST Last = (-Radix - Min) MOD Radix; Cut = ( Last + Min) DIV Radix; BEGIN ASSERT(pre <= 0) RETURN (pre > Cut) OR (pre = Cut) & (digit <= Last) END InRange;
PROCEDURE Parse(s: ARRAY OF CHAR; VAR ofs: INTEGER; VAR val: INTEGER): INTEGER; VAR d, mark, i: INTEGER; neg: BOOLEAN; BEGIN i := ofs; neg := s[i] = "-"; IF neg OR (s[i] = "+") THEN INC(i) END; IF ValDigit(s[i], d) THEN val := -d; INC(i); WHILE ValDigit(s[i], d) & InRange(val, d) DO val := val * Radix - d; INC(i) END; mark := Ok; IF ValDigit(s[i], d) OR ~neg & (val < -Max) THEN mark := ErrTooLarge ELSIF ~neg THEN val := -val END ELSE mark := ErrNoDigits END; ofs := i RETURN mark END Parse

Этот код верен и для систем, в которых Min = -Max

Комментариев нет:

Отправить комментарий