Рекомендации по предобработке скобочного выражения

В таблице 1.3 использованы следующие обозначения:

- символ ^ соответствует пустой входной строке и пустому стеку.

Ù - операция возведения в степень;

P - переменная;

F – любая функция (унарная операция);

1 - поместить символ из входной строки в стек;

2 - извлечь символ из стека и отправить его в выходную строку;

3 - удалить символ ")" из входной строки и символ "(" из стека;

4 - успешное окончание преобразования;

5 - ошибка скобочной структуры;

6 - переслать символ из входной строки - в выходную строку;

7 - ошибка: после функции отсутствует "(".

Заметим, что здесь содержимое действия 3 изменилось в сравнении с таблицей 1.2.Это связано с введением в рассмотрение функций.

Использование памяти со стековой адресацией на этапе преобразования инфиксной формы в постфиксную форму иллюстрирует рисунок 1.1.

Текущее состояние постфикс­ного выражения:		Исходное инфиксное выраже­ние (обраба­тывается по символам слева - направо):
a b c d e		a + b * sin(c - d / e)

Результирующее постфиксное выражение: a b c d e / - sin * +

Рисунок 1.1 - Использование стековой памяти в процессе
получения постфиксной формы выражения

На рисунке 1.1 стрелки указывают возможные направления перемещения символов. В ситуации, изображенной на рисунке 1.1, все содержимое стека (кроме символа "(") должно быть через его вершину передано в выходную строку и "приклеено" к ней справа. Получится следующее выражение в постфиксной форме: a b c d e / - sin * +.

Рекомендации по предобработке скобочного выражения

В процессе преобразования выражения в постфиксную форму необходимо обнаруживать имена функций, которые всегда задаются строками символов. Это приводит к невозможности использования оператора case для организации ветвления алгоритма. Использование же оператора if делает структуру алгоритма менее наглядной. Кроме того, использование строкового типа для элементов стека приводит к применению отношений "равно/не равно" между строковыми переменными и константами. Сравнение строковых типов осуществляется более сложно, чем сравнение символьных типов. Поэтому представляется целесообразным выполнить такое преобразование исходной строки-выражения, после которого можно будет оперировать не строковыми типами, а символьными. С этой целью предлагается исходную строку в инфиксной форме подвергнуть обработке, в результате которой:

- из входной строки удаляются все пробелы;

- все подстроки, задающие функции, заменяются символами некоторого алфавита А1 по правилу, заданному таблицей соответствия имен функций и символов алфавита А 1(таблица может быть задана как массив-константа в тексте программы);

- все подстроки, задающие числа, заменяются символами некоторого алфавита А 2: первое число заменяется первым символом алфавита, второе число - вторым символом и т.д.

Алфавиты А 1 и А 2 не должны иметь общих символов.

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

Приводимая ниже таблица 1.4 дает пример соответствия имен некоторых наиболее часто используемых функций символам алфавита А 1, в качестве которого в данном случае взяты строчные символы русского алфавита. При использовании такой таблицы исходное выражение, например, sin(arcsin(x ^2)), будет преобразовано в выражение в(а(x ^2)).

Таблица 1.4

Соответствия имен функций
и символов алфавита А 1

Можно предложить, по крайней мере, два подхода к замене имен функций на символы алфавита A1.

Const

TableSize = 23;

Table: array [ 1..TableSize, 1..2 ] of string [ 6 ] =

(('arcsin', 'а'), ('arccos', 'б'), ('sin', 'в'),

('cos', 'г'), ('arcctg', 'д'), ('arctg', 'е'),

('ctg', 'ж'), ('tg', 'з'), ('ln', 'и'),

('arsh', 'к'), ('arch', 'л'), ('arth', 'м'),

('arcth', 'н'), ('sh', 'о'), ('ch', 'п'),

('cth', 'р'), ('th', 'с'), ('abs', 'т'),

('exp', 'у'), ('lg', 'ф'), ('round', 'х'),

('trunc', 'ц'), ('fruc', 'ч'));

Для получения менее разветвленного алгоритма в части, обеспечивающей выбор значения из таблицы решений, полезно ввести вспомогательные переменные, задающие номера строк и столбцов таблицы (таблица 1.5).

Таблица 1.5

В таблице 1.5:

a - номер варианта символа во входной строке;

b - номер варианта символа в вершине стека;

число в таблице = a + 10 b.

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

Мысленно совместив таблицу 1.5 с таблицей 1.3, получим соответствие между значением выражения a + 10 b из таблицы 1.5 и вариантом поведения алгоритма преобразования выражения к постфиксной форме из таблицы 1.3

1.2.3. Программная реализация некоторых функций
алгоритма преобразования

На языках программирования Pascal и Delphi алгоритм, обеспечивающий выбор варианта поведения алгоритма преобразования выражения к постфиксной форме, можно реализовать, например, следующим образом (см. далее Function SymbNumInputStr, Function Pop, Function SymbNumInStek, Procedure CreatePostfix).

Функция SymbNumInputStr столбцам таблицы 1.5 ставит в соот­вет­ствие номера от 1 до 9 (слева-направо).

Function SymbNumInputStr(Symb: char): byte;

Begin

if Symb = #0

then SymbNumInputStr:= 1 {для Delphi: Result:= 1}

else case Symb of

'+': SymbNumInputStr:= 2; {для Delphi: Result:=2}

'-': SymbNumInputStr:= 3; {для Delphi: Result:=3}

'*': SymbNumInputStr:= 4; {для Delphi: Result:=4}

'/': SymbNumInputStr:= 5; {для Delphi: Result:=5}

'^': SymbNumInputStr:= 6; {для Delphi: Result:=6}

'(': SymbNumInputStr:= 7; {для Delphi: Result:=7}

')': SymbNumInputStr:= 8; {для Delphi: Result:=8}

'а'..'п', 'р'..'я': {очередной символ - функция}

SymbNumInputStr:= 9; {для Delphi: Result:=9}

'A'..'Z': {очередной символ - переменная}

SymbNumInputStr:= 10; {для Delphi:Result:=10}

end; {case}

end; {SymbNumInputStr}

Функция Pop считывает из стека один элемент.

const StekSize = 100; {т.е. глубина стека 100 элементов}

type TStek = record

StekArr: array [1..StekSize] of Char;

StekPointer: byte

{Указывает на первое свободное место в стеке.

StekPointer = 1 указывает на дно стека}

end;

Function Pop(var Stek: TStek; var StekData: Char): boolean;

Begin

with Stek do

Begin

if StekPointer > 1

{StekPointer=1 указывает на дно стека}

Then begin

Pop:= TRUE; {- считывание из стека закончилось успешно} {для Delphi: Result:=TRUE}

Dec(StekPointer);

StekData:= StekArr[ StekPointer ]

End

else Pop:= FALSE {- стек пустой: считывать нечего } end {with Stek do}

end; {Pop}

Функция SymbNumInStek строкам таблицы ставит в соответствие номера от 0 до 7 (сверху-вниз).

Function SymbNumInStek: byte;

var LastSymbInStek: Char;

Begin

if Pop(Stek, LastSymbInStek)

then case LastSymbInStek of

'+': SymbNumInStek:= 1; {для Delphi: Result:=1}

'-': SymbNumInStek:= 2; {для Delphi: Result:=2}

'*': SymbNumInStek:= 3; {для Delphi: Result:=3}

'/': SymbNumInStek:= 4; {для Delphi: Result:=4}

'^': SymbNumInStek:= 5; {для Delphi: Result:=5}

'(': SymbNumInStek:= 6; {для Delphi: Result:=6}

else SymbNumInStek:= 7 {- символ функции (переменные в стек не попадают)}

end {case}

else SymbNumInStek:= 0 { - стек пуст}

end; {SymbNum In Stek}

Ниже приведен один из вариантов реализации процедуры преобразования исходного выражения, заданного строкой InputStr, записанной в инфиксной форме, в постфиксную форму записи, заданную выходной строкой OutputStr.

Begin

OutputStr:= '';

Stek.StekPointer:= 1; {- это "очистка стека"}

Repeat

case SymbNumInputStr(InputStr[1])+10*SymbNumInStek of

{ SymbNumInputStr + 10 * SymbNumInStek º a + 10 b}

2..7, 9, 14..17, 19, 24..27, 29, 36, 37, 39, 46, 47, 49, 57, 59, 62..67, 69, 77: Выполняем действие 1 из табл. 1.3

11..13, 21..23, 31..35, 41..45, 51..56,18,28,38,48,

58, 71..76: Выполняем действие 2 из табл. 1.3

68: Выполняем действие 3 из табл. 1.3

1: Выполняем действие 4 из табл. 1.3

8, 61: Выполняем действие 5 из табл. 1.3

10, 20, 30, 40, 50, 60, 70: Выполняем действие 6 из табл. 1.3

78, 79: Выполняем действие 7 из табл. 1.3

end; {case}

Until FALSE {выход через действие 4 из табл. 1.3 }

end; {CreatePostfix}

Ниже приведен второй вариант реализации процедуры CreatePostfix: Алгоритм использует таблицу решений, заданную явно в тексте программы. При этом отпадает необходимость использования таблицы 1.5.

type TTRArr = array [ 0..7, 1..10 ] of byte;

{********* ТАБЛИЦА РЕШЕНИЙ: *********}

const TR: TTRArr = ((4, 1, 1, 1, 1, 1, 1, 5, 1, 6),

(2, 2, 2, 1, 1, 1, 1, 2, 1, 6),

(2, 2, 2, 1, 1, 1, 1, 2, 1, 6),

(2, 2, 2, 2, 2, 1, 1, 2, 1, 6),

(2, 2, 2, 2, 2, 1, 1, 2, 1, 6),

(2, 2, 2, 2, 2, 2, 1, 2, 1, 6),

(5, 1, 1, 1, 1, 1, 1, 3, 1, 6),

(2, 2, 2, 2, 2, 2, 1, 7, 7, 6));

Procedure CreatePostfix;

Begin

OutputStr:= '';

Stek.StekPointer:= 1; {- это "очистка стека"}

Repeat

case TR[SymbNumInStek, SymbNumInputStr(InputStr[1])] of

1: Выполняем действие 1 из табл. 1.3

2: Выполняем действие 2 из табл. 1.3

3: Выполняем действие 3 из табл. 1.3

4: Выполняем действие 4 из табл. 1.3

5: Выполняем действие 5 из табл. 1.3

6: Выполняем действие 6 из табл. 1.3

7: Выполняем действие 7 из табл. 1.3

end; {case TR}

Until FALSE {выход через действие 4 из табл. 1.3}

end;

В процессе преобразования выражения к постфиксной форме можно обнару­жить лишь некоторые ошибки, например:

- непра­вильную скобочную структуру выражения;

- отсутствие символа ( после имени функции.

Для более полного и тонкого синтаксического анализа необходимо применять дополнительные алгоритмы.

1.2.4. Пример пошагового моделирования
преобразования инфиксного выражения

Рассмотрим действие алгоритма на примере следующего выражения: sin(cos(56 - 8)^38.6 - 2)

1. Заменим имен функций символами алфавита A 1 (таблица 1.4).

1.1. sin заменим на "в". Получим: в(cos(56-8)^38.6-2);

1.2. cos заменим на "г". Получим: в(г(56-8)^38.6-2);

2. Заменим числа символами алфавита A 2 (возьмем в качестве алфавита А2 прописные буквы латинского алфавита)

2.1. Заменим число 56 первым символом алфавита A 2 (буквой A). Получим: в(г(A -8)^38.6-2).

2.2. Заменим число 8 вторым символом алфавита A 2 (буквой B). Получим: в(г(A - B)^38.6-2).

2.3. Заменим число 38,6 третьим символом алфавита A 2 (буквой C). Получим: в(г(A - B)^ C -2).

2.4. Заменим число 2 четвертым символом алфавита A 2 (буквой D). Получим: в(г(A - B)^ C - D).

3. Преобразуем полученное выражение "в(г(A - B)^ C - D)" к постфиксной форме.

Подробно это преобразование рассматривается ниже.

В результате преобразования будет получено следующее выражение: AB -г C ^ D -в.

Теперь остается только заменить символы алфавита A 1 на соответст­вующие им функции и символы алфавита A 2 на соответствующие им числа. В результате, выражение sin(cos(56-8)^38.6-2)будет преобразовано в постфиксную форму: 56 8 - cos 38.6 ^ 2 – sin.

2. моделирование вычисления выражений,
представленных в постфиксной форме

2.1. Описание алгоритма вычисления значения выражения,
представленного в постфиксной форме записи

Наиболее простой алгоритм вычисления выражения по его постфиксной форме строится на основе стековой адресации памяти. В этом алгоритме строка символов, задающая выражение, просматривается слева - направо, при этом:

- очередной операнд «заталкивается» в стек через его вершину;

- при встрече очередного символа операции или функции из стека через его вершину извлекается необходимое число операндов этой операции или аргументов функции. Затем, выполняется операция (или вычисля­ется функция) и результат вычисления «заталкивается» в стек через его вершину;

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

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

- следование друг за другом символов операций;

- пропуск символа операции;

- отсутствие аргумента у функции или недостаточное количество операндов в двухместной операции.

2.2. Пошаговое выполнение алгоритма вычисления значения
выражения, представленного в постфиксной форме записи

Для получения более полного представления о взаимодействии алгоритма преобразования выражения, записанного в инфиксной форме - в постфиксную и алгоритма вычисления значения выражения по постфиксной форме рассмотрим действие алгоритма вычисления на примере функции sin(cos(56-8)^38,6-2).

Эта функция была ранее преобразована к постфиксной форме вида: 56 8 - cos 38,6 ^ 2 - sin.При этом, в процессе преобразования исходного инфиксного выражения имена функций и числа были заменены символами двух алфавитов и была получена постфиксная форма выражения следующего вида:

AB -г C ^ D -в,

где A, B, C и D - символы алфавита A 2, обозначающие числа;

г - обозначение функции cos;

в - обозначение функции sin.

Именно это последнее выражение используем для иллюстрации процесса вычислений на основе постфиксной формы записи выражения.

1. В начале входной строки AB -г C ^ D -в имеем символ A алфавита A 2 - число. Отправим в стек число 56, соответствующее символу A.

2. В начале входной строки B -г C ^ D -в имеем символ B алфавита A 2 - число. Отправим в стек число 8, соответствующее символу B.

3. В начале входной строки -г C ^ D -в имеем символ "-" - бинарную операцию. Учтем, что операнд, находящийся в вершине стека, должен стоять справа от знака двухместной операции (это 8), а операнд, находящийся под вершиной стека, должен стоять слева от знака операции (это 56). Извлечем из стека два верхних операнда (числа 8 и 56), выполним операцию "-" (56-8) и ее результат (48) поместим в стек.

4. В начале входной строки г C ^ D -в имеем символ г алфавита A 1, обозначающий функцию cos. Достанем из стека аргумент функции (число 48), вычислим значение функции, и результат поместим в стек.

5. В начале входной строки C ^ D -в имеем символ C алфавита A 2 - число. Отправим в стек число 38,6, соответствующее символу C.

6.В начале входной строки ^ D -в имеем символ "^". Достанем из стека два операнда и, выполнив операцию "0,6691306 ^ 38,6", поместим ее результат (1,8395879e-7) в стек.

7.В начале входной строки D -в имеем символ D алфавита A 2 - число. Отправим в стек число 2, соответствующее символу D.

8. В начале входной строки имеем символ "-" - бинарную операцию. Достанем из стека два операнда и, выполнив операцию, поместим ее результат в стек.

9. В начале входной строки имеем символ в алфавита A 1 - функцию. Достанем из стека операнд -1,9999998 – аргумент функции и, вычислив функцию sin(-1,9999998), поместим результат в стек.

10. Входная строка пуста, поэтому в стеке по его указателю находится искомое значение выражения, равное -0,0348995.

Итак, sin(cos(56-8)^38,6-2) = -0,0348995.

В рассмотренном примере результаты вычислений даны с точностью меньшей, чем обеспечивает компьютер.

2.3. Мультимедийная обучающая система
”Трансляция алгебраических выражений”

На кафедре «Вычислительная техника» СамГТУ имеется “ Мультимедийное обучающее приложение ”Трансляция алгебраических выражений”, разработанное на основе изложенных методов и алгоритмов. Это приложение поддерживает следующие функции.

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

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

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

4. Каждое действие сопровождается словесными голосовыми комментариями (при желании звуковое сопровождение можно отключить), способствующими лучшему восприятию представляемых алгоритмов и позволяющими проводить занятия в отсутствии лектора.

3. Элементы теории вероятностей
и математической статистики

Мы поможем в написании ваших работ!