16.3 Каноническая форма арифметических выражений

Известно, что одно и то же по значению арифметическое выражение может иметь различный вид. Например, используя свойства ассоциативности для сложения, или коммутативности для умножения, можно получить достаточно большое количество эквивалентных арифметических выражений. Ниже предлагается итерационный алгоритм приведения некоторого арифметического выражения в каноническую форму. Под канонической формой арифметического выражения будем понимать выражение со следующими свойствами:
       1)все аддитивные составляющие разделены на два класса: сложения и вычитания и в каждом классе произведено лексикографическое упорядочение членов;
       2)все мультипликативные составляющие для каждого узла <T> разделены на два класса: умножения и деления и в каждом классе произведено лексикографическое упорядочение;
       3)раскрыты все возможное скобки;
       4) произведены следующие преобразования:
              -сложение и вычитание с нулем;
              -умножение и деление на единицу;
              -умножение на ноль;
              -приведены подобные члены;
              -произведено вычисление составляющих, состоящих из констант.
       Итак, чтобы получить каноническую форму, необходимо итеративно проделать следующие действия:
       1. произвести лексикографическое упорядочение;
       2. раскрыть скобки;
       3.произвести сложение и вычитание с нулем, умножение на ноль, умножение и деление на единицу, привести подобные члены и произвести вычисление составляющих состоящих из констант.
       Итеративность процесса получения канонической формы заключается в том, что если будет произведено хоть одно преобразование на шагах 2, 3, то необходимо заново произвести лексикографическое упорядочение.