Пример вычисления арифметического выражения с помощью стеков

End.

IMPLEMENTATION

Procedure Push;

Var t:u;

Begin New(t); t^.i:= a; t^.L:= h; h:= t; End;

Function Pop;

Var t:u;

Begin Pop:= h^.i; t:= h; h:= h^.L; Dispose (t); End;

Function Empty; Begin Empty:= h = Nil; End;

Function Top; Begin Top:= h^.i; End;

Одно из интереснейших применений стека - синтаксический раз­бор и вычисление выражения, например, арифметического. Пусть дана строка, являющаяся записью арифметического выражения. Возможно наличие бинарных операций '+', '-', '*', '/', левой и пра­вой круглых скобок, в качестве операндов для простоты будем ис­пользовать цифры от 0 до 9. Выражение заканчивается знаком '='. Например, допустимым будет выражение 4-2/6*(2+3*6)=. Необхо­димо написать программу, вычисляющую значение этого выраже­ния или выдающую сообщение об ошибке в нем.

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

1.Операции выражения в скобках выполняются первыми, т.е.
имеют наивысший приоритет. Для выражения, находящегося в
скобках, правила вычисления выражения те же, что и для обычного
выражения.

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

3.Операции с равными приоритетами выполняются в порядке их появления в выражении.

Рассмотрим для начала выражение без скобок, например 8/2+3*4=. Сначала надо выполнить деление, далее - умножение, а затем - сложение. Причем складывать надо результаты первой и второй операций. Будем разбирать выражение по символу. Первый символ 8 - операнд, он нам понадобится позже, поэтому временно поместим его в стек операндов. Следующий символ - знак деления. Мы не знаем, что нам встретится позднее, возможно скобка, поэ­тому надо ли выполнять деление прямо сейчас, мы сказать не можем. Следовательно, поместим на время этот символ в стек опе­раций. Следующий символ - тоже операнд, и мы поместим его в стек операндов. Далее идет знак сложения. Посмотрим, какие опе­рации встречались до сложения, не надо ли их выполнить раньше. На вершине стека операций находится символ операции деления. Операция деления имеет больший приоритет, чем операция сложе­ния, поэтому выполним теперь деление. Для этого вынем знак опе­рации деления из стека операций, а также возьмем из стека операндов два верхних операнда: сначала - правый (2), затем -левый (8). Поделим левый операнд на правый. Получим значение 4. Оно понадобится нам и позже, поэтому временно положим его в стек операндов. Теперь текущим рассматриваемым символом яв­ляется знак сложения. Если в стеке операций есть еще элементы, которые надо выполнить до сложения, то выполним их. Но у нас стек пуст. Какие операции встретятся дальше, мы не знаем, поэтому поместим пока знак сложения в стек операций и перейдем к сле­дующему символу. Это операнд 3, поместим его в стек операндов. Перечислим снизу вверх элементы стека операндов: (4, 3). Далее следует знак умножения. Проверим, не было ли у нас операций, которые должны были быть до него выполнены (например, другое умножение). Верхним элементом в стеке операций у нас является знак сложения, так как умножение должно выполняться раньше, по­местим его в стек над сложением. Таким образом, стек операций выглядит в следующим виде: ('+','*'). Следующий символ - опе­ранд 4. Поместим его в стек операндов, в котором теперь будут храниться уже три элемента: (4, 3, 4). Следующий символ - знак равенства, означающий конец выражения. На вершине стека опе­раций у нас знак умножения. Выполним эту операцию, вынув ее из стека и взяв два верхних операнда из стека операндов. Левый операнд у нас 3, а правый - 4. Результатом умножения будет 12. Поместим этот результат в стек операндов, теперь там два элемен­та: (4, 12). На вершине стека операций находится знак сложения. Выполним эту операцию. Левым операндом будет 4, правым - 12. Результатом будет 16, поместим 16 в стек операндов. Стек операций пуст, значит, в стеке операндов у нас находится результат. Удалим его из стека и выведем на экран. У нас получился верный результат вычисления выражения 8/2+3*4.

Заметим, что для элементов стека операндов неудобно исполь­зовать тип Char, как для элементов стека операций. Целесообразно элементы стека операндов объявить как вещественные числа.

Схема алгоритма:

1. 8 à Sd; (Sd – стек операндов (данных))

2. / à So; (So – стек операций)

3. 2 à Sd;

4. +; смотрим Sо, там /, p(/) > p(+), поэтому выполним операцию /;

8: 2 = 4 à Sd.

5. Смотрим So. Если So ≠ Ǿ и p (операции) > p(+), то эти операции

должны быть выполнены. Но у нас So= Ǿ, поэтому

+ à So.

6. 3 à Sd;

7. *: смотрим So → там +; так как p (+) < p(*), поэтому

* à So;

8. 4 à Sd;

9. = конец выражения.

4 * 3 = 12 à Sd;

4 +12 = 16 à Sd;

Sd à Ответ =16

Теперь посмотрим, какие необходимо выполнить действия, если в выражении есть скобки. В качестве примера разберем выражение 4*(2+3)=. Первый символ - операнд. Поместим его в стек операн­дов. Следующий символ - знак умножения. Операций, которые надо было выполнить до него, у нас нет, поэтому поместим этот символ в стек операций. Далее следует левая скобка. Это означает, что то, что будет записано далее, должно вычисляться раньше, чем то, что мы рассматривали до сих пор. Поместим левую скобку в стек операций, состояние стека: ('*','('). Далее у нас следует операнд. По­местим его в стек операндов, состояние стека операндов: (4, 2). Сле­дующий символ - знак сложения. На вершине стека находится скобка, таким образом, у нас нет ничего, что надо было выполнить до сложения. Поместим сложение в стек операций, который теперь содержит три элемента: ('*','(','+'). Следующий символ - операнд. Поместим его в стек операндов, который теперь имеет следующее содержимое: (4, 2, 3). Далее у нас идет правая скобка, следователь­но, выражение в скобках на этом заканчивается, надо его вычис­лить. Верхней операцией у нас является сложение, выполним его. В стеке операций у нас теперь два элемента: ('*', '('), в стеке опе­рандов – тоже два: (4, 5). Выполним все операции, которые содер­жались в скобках, удалим из стека операций левую скобку (если ее в стеке нет, значит, в выражении была допущена ошибка). Перей­дем теперь к следующему символу. Это знак '=', означающий конец выражения. Выполним верхнюю операцию в стеке – умножение. Те­перь стек операций у нас пуст, а в стеке операндов хранится число 20. Это и есть результат вычисления нашего выражения.

Итак, для каждого символа в выражении предусмотрены раз­личные действия, причем действия с операциями зависят не только от самой операции, но и от того, что находится на вершине стека операций. Рассмотрим возможные варианты.

Для символов '+' и '-' правила одинаковы:

1. Если стек пуст или верхний элемент - левая скобка, поместим
операцию в стек и перейдем к следующему символу.

2. Если на вершине стека операция с равным приоритетом, вы­полнить ее, поместить рассматриваемую в данный момент опера­цию в стек и перейти к следующему символу.

3. Если на вершине стека операция с высшим приоритетом, вы­полнить эту операцию. Так как возможно, что до сложения или вы­читания встретилась не одна операция, которая должна быть выполнена раньше рассматриваемой в данный момент, то к следующему символу пока не переходим.

Правила для операций умножения и деления (для символов '*' и '/').

1. Если стек пуст или на вершине находится левая скобка или операция с меньшим приоритетом, операция помещается в стек, и переходят к следующему символу.

2. Если на вершине стека находится операция с равным при­оритетом, необходимо выполнить ее и поместить рассматриваемую в данный момент операцию в стек и перейти к следующему сим­волу.

В случае левой скобки необходимо добавить символ в стек опе­раций и перейти к следующему символу.

В случае правой скобки возможны следующие варианты:

1. Стек пуст. Следовательно, не хватает левой скобки, т.е. вы­ражение ошибочно.

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

3. На вершине стека - арифметическая операция. Вынимаем опе­рацию из стека и выполняем ее.

И наконец, рассмотрим действия, необходимые для обработки символа конца выражения.

1.Если стек пуст, то выражение вычислено. Следовательно, нужно удалить из стека операндов результат и вывести его.

2. На вершине - левая скобка. Следовательно, левых скобок в выражении было больше, чем правых, т.е. выражение ошибочно.

3. На вершине стека - арифметическая операция. Необходимо удалить ее из стека и выполнить.

Итак, у нас шесть возможных вариантов действий. Для выбора того или иного действия необходимо проверить сочетание состо­яния вершины стека операций и рассматриваемый символ. Чтобы ускорить выбор нужной операции, составим матрицу, элементы ко­торой будут соответствовать номеру действия, необхо

	текущая операция из входной строки
=	(	+	-	*	/	)
вершина стека операций	пусто
(
+
-
*
/
Табл. 5.2. Таблица решений для выбора действия.

димого при данном состоянии стека и данной операции (табл.5.2.). Состояние стека оп­ределяется номером строки, операция - номером столбца. Обозна­чим состояние ошибки числом 0, а остальным вариантам присвоим номера от 1 до 5:

0 – ошибка;

1 – положить операцию в стек и перейти к следующему символу
выражения;

2 – выполнить верхнюю операцию, положить рассматриваемую
операцию в стек и перейти к следующему символу выражения;

3 – извлечь из стека операций верхний элемент и перейти к следующему символу выражения;

4 – выполнить верхнюю операцию;

5 – состояние конца выражения.

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

Program Compute;

Uses CRT, So, Sd; { So –стек для знаков операций;

Sd – стек для данных. }

Const tab: Array [0..5,0..6] Of Byte =((5, 1, 1, 1, 1, 1, 0),

(0, 1, 1, 1, 1, 1, 3),

(4, 1, 2, 2, 1, 1, 4),

(4, 1, 2, 2, 1, 1, 4),

(4, 1, 4, 4, 2, 2, 4),

(4, 1, 4, 4, 2, 2, 4));

Var ho:w; h:u; { указатели для стеков операций и данных}

v:String; {в v исходное арифметическое выражение }

Ok, f:Boolean; {флаги корректности и завершения}

j, k:Integer; c:Char; res, x:Real; {рабочие переменные}

.......................................................................................................................................

Function NumAct (sp:w; op:Char):Byte;

{ возвращает номер действия из таблицы tab; op – операция из вх. строки v }

Var i:Byte;

Дата добавления: 2014-01-11