Компьютерное представление и обработка формул

1. Скобочная запись

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

а) $m=2^{2^n}$

б) $a=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3}}}$

в) $y=x\sin{x^2}+{\sqrt[3]{x}}-3\log_2{x}$

Формула чем-то напоминает иероглиф: от того, выше или ниже записан значок, короче или длиннее проведена линия, зависит порой смысл всей формулы. Формулу всегда стараются записать красиво. Попробуем «мысленно» ввести записанные формулы в компьютер. Как нам сразу начинает мешать их «красивая запись»! Ведь ввод с клавиатуры «многоэтажной» формулы предполагает выстраивание всех символов в очередь.

Запишем формулу по другому - в строку. Такую запись используют во всех алгоритмических языках. И тут не обойтись без скобок:

а) m=2^(2^n)

б) a=a0+1/(a1+1/(a2+1/a3))

в) y=x*sin(x^2)+x^(1/3)3*(ln(x)/ln(2))

Запись стала выглядеть куда менее привлекательно, зато теперь понятно, как ее вводить в компьютер: посимвольно, слева-направо.

При записи формул в строку используют дополнительные договоренности, позволяющие уменьшить число скобок. Так, сочетательный закон позволяет, вместо скобочных записей (a+b)+c и a+(b+c), писать просто a+b+c. То же верно для умножения. А вот для вычитания и деления сочетательный закон не выполняется: (ab)c≠a(bc). Конечно, скобки в этом случае можно «раскрыть», но тогда получим, вообще говоря, другую формулу.

Другим способом уменьшения количества скобок в записи является использование приоритетов: операциям умножения и деления присваивается больший приоритет по отношению к операциям сложения и вычитания. Это означает, что при отсутствии скобок в записи сначала выполняются операции большего приоритета (умножение и деление), а затем меньшего (сложение и вычитание). Например, в следующей формуле скобки в правой части опускаются a*(b+c)=a*b+a*c.

Наконец, если операции одного приоритета выполняются в порядке их появления в строке, то скобки тоже можно опустить. Например, формула ((a+b)c)d записывается без скобок a+bcd.

Разберем одну из задач, связанную с анализом скобочной записи формулы. Рассмотрим формулы, в которых разрешено использовать переменные, константы, арифметические операции сложения, вычитания, умножения и деления и три типа скобок: фигурные, квадратные и круглые. Требуется проверить, имеет ли формула правильную скобочную структуру. Будем говорить, что формула имеет правильную скобочную структуру, если выполняются следующие условия:

  1. При просмотре формулы слева направо в любой момент времени число просмотренных закрывающих скобок меньше или равно числу просмотренных открывающих скобок.
  2. В формуле число открывающих скобок равно числу закрывающих.
  3. Скобки трех типов согласованы, то есть открывающей круглой скобке «(» должна соответствовать закрывающая круглая скобка «)», открывающей квадратной скобке «[» должна соответствовать закрывающая квадратная скобка «]», и, наконец, фигурной скобке «{» фигурная скобка «}»

Формула [A+B*(C+D)]*{(AB/C)/K+L} имеет правильную скобочную структуру. Формула (A+B))*(C+D) имеет неправильную скобочную структуру: нарушено первое условие. Следующая формула ((A+B) имеет также неправильную скобочную структуру: нарушено второе условие. В следующей формуле [A+B)(C+D] неправильная скобочная структура, потому что скобки в формуле несогласованны.

Задача 1. Теоретическая. При записи формулы ученик постоянно путает круглые, квадратные и фигурные скобки. При этом он не путает открывающие и закрывающие скобки. Предложите алгоритм исправления ошибок ученика. Используйте для этого алгоритм анализа скобочной структуры, приведенный в указании. Проиллюстрируйте работу построенного алгоритма на следующей формуле: ((({a/(b*[cd)}]+e]/(fg}}]. Как модифицировать этот алгоритм, чтобы в исправленной формуле вложенные скобки чередовались (круглые квадратные фигурные круглые).

Практическая. Напишите программу, которая, получив в качестве исходных данных формулу, определяет, имеет ли она правильную скобочную структуру.

Указание. Для построения алгоритма анализа скобочной структуры формулы полезно использовать стек. Тогда алгоритм решения задачи может быть следующим. Просматриваем символ за символом, причем, встретив открывающую скобку, помещаем ее в стек, а встретив закрывающую скобку, сравниваем ее со скобкой на вершине стека. Если там оказывается открывающая скобка соответствующего типа, то верхняя скобка из стека удаляется, иначе скобочная запись является неправильной. Для того чтобы обойти ситуацию, связанную с исчерпанием стека, если в исходной формуле закрывающих скобок оказывается больше, чем открывающих, поместим в стек так называемый маркер (символ, который не может встретиться в формуле). Символы, не являющиеся скобками, будем просто игнорировать.

Формат ввода:

Формула, записанная строкой символов.

Формат вывода:

Результат анализа: «правильная запись скобок» или «неправильная запись скобок».

2. Бесскобочная запись

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

Для этого надо найти действие, которое может быть выполнено первым, выделить операнды, выполнить это действие, а затем повторить операции с «укороченной» строкой, в которой вычисленная формула обозначена одним символом. При определении порядка вычислений нужно уметь сравнивать приоритеты операций, находить выражения, заключенные в скобки. Все это не так просто.

Поставим задачу шире: как автоматизировать работу с формулами. Мы имеем «внешнее» для компьютера представление, неудобное для автоматической обработки, хотим же перейти к другому «внутреннему» представлению, для которого автоматическая обработка формул будет обеспечиваться простыми, но эффективными алгоритмами.

Оказывается, можно придумать другие, более удобные для вычислений, способы задания формулы строкой. Наиболее известные и употребимые префиксная и постфиксная записи. Как же они определяются?

Для простых формул типа a+b постфиксная запись выглядит как ab+, а префиксная +ab, то есть мы просто перемещаем знак операции (который по традиции ставится между операндами, и поэтому обычную запись называют еще инфиксной) после перечисления операндов или перед ними. Обратим внимание, что для операций с одним аргументом, таких как воз- ведение в степень или извлечение корня, мы обычно употребляем постфиксную или префиксную записи:

x^2 - действие записано после аргумента (постфиксная запись).

\sqrt{x} - действие записано перед аргументом (префиксная запись).

Как же строить префиксную и постфиксную записи формулы, которая содержит большее количество операций, например, (a+b*c)/(dc)?

Воспользуемся общим приемом: сведем задачу к уже решенной. Для этого выделим последнюю выполняемую операцию и перенесем ее в конец (для постфиксной) или в начало (для префиксной) записи: [a+b*c][dc]/, где в квадратных скобках стоят необработанные части формулы. Далее применим этот алгоритм к формулам в скобках.

Будем так действовать, пока не останется ни одной необработанной части формулы: abc*+dc/. Последняя строка и есть постфиксная запись исходной формулы.

Задача 2. Теоретическая. а) преобразуйте формулу из задачи 1 в постфиксную и префиксную форму; б) пусть формула наряду со знаками арифметических операций содержит операции возведения в квадрат и извлечения квадратного корня. Например: (a*b*c)/ √((ab)2+(bc)2+(ac)2).

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

Первому символу постфиксной записи, который всегда является буквой для правильных записей, сопоставляем 1. Каждому следующему число на 1 большее предыдущего, если это буква, и число на 1 меньшее, если это знак операции.

Так, для нашего примера получим такую запись: 

    a b c * + d e  /
    1 2 3 2 1 2 3 2 1

Признаком того, что запись формулы правильная, является последняя единица. То, что это условие необходимо, понятно. Ведь в любой правильной формуле число букв на 1 больше числа операций. Но является ли это условие достаточным? Иными словами, будет ли любой последовательности чисел, начинающейся и заканчивающейся единицей и обладающей свойством, что любые два соседних числа отличаются ровно на единицу, соответствовать некоторая формула?

Оказывается, да! Например, другая последовательность, состоящая также из 9 чисел: 121234321, соответствует, в частности, такой формуле:

ab*cdе+/ или a * b c (d e)−

Задача 3. Уровень 1.

а) Перечислите все «правильные» последовательности из 9 чисел, то есть последовательности натуральных чисел, начинающиеся и заканчивающиеся единицей, у которых соседние числа отличаются на единицу. Постройте по ним формулы, используя буквы a, b, c, d, e и знаки опера- ций *, +, , / в указанном порядке.

б) Может ли последовательность с указанными выше свойствами состоять из четного количества чисел?

в)* Придумайте способ, как подсчитывать количество «правильных» последовательностей, зная количества более коротких последовательностей. Найдите количество «правильных» последовательностей из 11 чисел.

Уровень 2. В произведении n чисел а1, а2, а3, ..., аn требуется расставить скоб- ки, полностью определяющие порядок вы- числения произведения, всеми возможны- ми способами. Напишите программу, вы- полняющую эту работу. В качестве про- веряемого результата подсчитайте коли- чество вариантов, начинающихся с двух открывающих скобок. Формат ввода: Число букв в последовательности. Формат вывода: Число вариантов. Пример. Ввод: 4 Вывод: 2

Пояснение. Последовательность abcd допускает следующие расстановки скобок: (((ab)c)d), ((ab)(cd)), ((a(bc))d), (a((bc)d)), (a(b(cd))). Различные расстановки скобок в инфиксной записи формулы соответству- ют различным «правильным» последова- тельностям, связанным с постфиксными записями формул. Поэтому «правильных» последовательностей из 2n1 чисел столько же, сколько вариантов расстанов- ки скобок в формуле с n переменными и n1 операциями. Число этих способов носит название чисел Каталана. Обозна- чая их за kn получаем: k1=1, k2=1, k3=2. Каждое следующее число Каталана выражается через предыдущие по форму- ле: kn+1=k1kn+k2kn1+...+knk1 Алгоритм восстановления формулы по постфиксной записи: ШАГ 1. Сделаем нумерацию символов строки по правилам, перечисленным выше. ЕСЛИ нумерация заканчивается еди- ницей, ТО запись формулы правильная и мож- но переходить к следующему шагу, ИНАЧЕ в постфиксной записи форму- лы имеется ошибка. ШАГ 2. Найдем предпоследнюю единицу в за- писи и разделим формулу на три части: 1-ая: все символы от первого до того, который помечен предпоследней еди- ницей включительно; 2-ая: все символы от помеченного предпоследней единицей до симво- ла, помеченного последней единицей, не включая их; 3-я: символ, помеченный последней единицей. Тогда первая часть записи - первый операнд, вторая часть - второй операнд, третья часть - знак последней выпол- няемой операции. Далее алгоритм нахождения последней выполняемой операции применяется к каждому из операндов.

Проиллюстрируем работу алгоритма на примере. a b * c d е + / 1 2 1 2 3 4 3 2 1 [a b *] / [c d е + ] 1 2 1 1 2 3 2 1 (a * b) / (c [d e +]) 1 2 1 ((a * b) / (c ( d + e ))) В предложенном алгоритме не указывалось, как записывать результат разбора постфиксной записи. В примере мы использовали привычную инфиксную скобочную запись. Обратите внимание, что каждую возникающую инфиксную запись мы брали в скобки. Разумеется, какие-то из них могли быть лишними (в нашем слу- чае лишней является пара внешних скобок). Алгоритм, который мы использовали в примере, порождает формулу в инфиксной за- писи, в которой расставлены все скобки.

3. ВЫЧИСЛЕНИЕ ЗНАЧЕНИЙ

У постфиксной записи есть замечательное свойство по ней очень легко производить вычисления значений формулы. Этот факт применяется в некоторых моделях калькуляторов. Для того чтобы описать алгоритм, воспользуемся структурой стека. Предположим, что формула состоит только из однобуквенных переменных (a, b, c, ..., z) и знаков операций (*, +, , /), а на вход алгоритма подается его правильная постфиксная запись. Алгоритм вычисления формулы в постфиксной форме с использованием стека чрезвычайно прост:

ПОКА в строке не кончатся символы, ПОВТОРЯТЬ Читаем очередной символ строки ЕСЛИ очередной символ - буква, ТО записываем в стек значение переменной, заданное этой буквой. ЕСЛИ очередной символ - знак опе- рации, ТО извлекаем последовательно два (верхних) числа из стека и выполня- ем над ними операцию, считая самое верхнее число значением второго опе- ранда; результат операции заносим в стек. КОНЕЦ ЦИКЛА Единственное оставшееся в стеке чис- ло и будет результатом вычисления формулы. Докажем корректность этого алго- ритма по индукции. База индукции. При n=1 правильная формула может состоять только из одной буквы, например, a. Тогда, в соответствии с алгоритмом, значение а будет записано в стек, и алгоритм закончит работу. Единственное чис- ло в стеке значение a и будет значением формулы. Для n=2 не существует правильной записи формулы. Для n=3 правильная запись формулы в постфиксной форме будет выглядеть, например, так: ab (разумеется, имена пе- ременных и знак операции могут быть другими). Нетрудно видеть, что работа по ал- горитму приведет к следующей последо- вательности состояний стека: