3. Применение стеков при разработке приложений
 

Одно из применений стеков можно продемонстрировать на примере вычисления значения арифметического выражения в калькуляторах. Пусть арифметическое выражение составлено из комбинации чисел, знаков бинарных арифметических операций (операторов) +,-,*,/,^, круглых скобок (,) и пробелов. Алгоритм вычисления предусматривает представление выражения в определенном формате. Различают представление выражения в инфиксной и постфиксной формах. В инфиксной форме записи каждый бинарный оператор помещается между двумя своими операндами. Для уточнения порядка вычислений могут использоваться круглые скобки. Инфиксный формат записи используется в большинстве языков программирования и калькуляторах и практически совпадает с естественной формой записи выражения. В постфиксной форме записи (обратной польской записи ОПЗ, или Reverse Polish Notation RPN) операнды предшествуют своему оператору. Примеры записи выражений:
Постфиксное выражение
5.7 6.8 + =
15 4*25 2/3-^ + =
3 7.5 * 6е2 5/+=
Инфиксное выражение
5.7+6.8=
15*4+(25/2-3)^2=
3*7.5+6е2/5=

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

Постфиксный калькулятор. Наиболее простым является алгоритм вычисления постфиксного выражения. Исходная строка содержит элементы только двух видов: числа и операторы. Пусть выражение заканчивается символом '='. Алго-ритм использует один стек, элементами которого являются числа вещественного типа. Алгоритм вычисления можно описать следующим образом.
1. Из исходной строки выделяется очередной элемент.
2. Если элемент — число, то оно заносится в стек. Переход к п.1.
3. Если элемент — оператор, то из стека последовательно извлекаются два элемента, сначала правый операнд, затем левый операнд и над ними выполняется операция, определенная оператором. Результат операции (число) заносится в стек. Переход к п.1.
4. Пункты 1 — 3 выполняются до тех пор, пока в исходной строке не встретится признак конца выражения '='. В этом случае число, находящееся в стеке, является результатом вычисления.

Рассмотрим порядок вычисления выражения
3 7.5 * 6е2 5/ + =
Шаг 1. Из строки выделяется число 3 и помещается в стек. Стек: 3.
Шаг 2. Из строки выделяется число 7.5 и помещается в стек. Стек: 3 7.5.
Шаг 3. Из строки выделяется оператор '*'. Из стека извле¬каются числа 7.5 и 3. Выполняется операция 3*7.5, результат 22.5 помещается в стек. Стек: 22.5.
Шаг 4. Из строки выделяется число 6е2 и помещается в стек. Стек: 22.5 600.
Шаг 5. Из строки выделяется число 5 и помещается в стек. Стек: 22.5 600 5.
Шаг 6. Из строки выделяется оператор 7'. Из стека извлекаются два числа 5 и 600. Выполняется операция 600/5, и результат 120 помещается в стек. Стек: 22.5 120.
Шаг 7. Из строки выделяется оператор '+'. Из стека извлекаются два числа 120 и 22.5. Выполняется операция 22.5+120. Ре¬зультат 142.5 засылается в стек.
Шаг 8. Из строки выделяется символ '=' — признак конца выражения. Из стека извлекается результат вычисления — число 142.5.

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

Алгоритм преобразования основан на методе стека с приоритетами. В нем всем операторам и скобкам-разделителям ставятся в соответствие целочисленные приоритеты. Чем старше операция, тем выше ее приоритет. Открывающая скобка имеет низший приоритет, равный 0, закрывающая скобка — равный 1.

В ходе обработки исходной строки операнды переносятся в выходную строку непосредственно, а операторы — через стек в соответствии со своими приоритетами. Элемент стека состоит из двух полей:

• оператор или скобка — символьный тип;
• приоритет — целочисленный тип.

Приоритет пустого стека полагаем равным нулю.

Алгоритм метода состоит в следующем.
1. Из исходной строки выделяется очередной элемент S_i.
2. Если S_i — операнд, то записать его в выходную строку, перейти к п.1; иначе перейти к п.З.
3. Если приоритет S_i равен нулю (т.е. элемент — открывающая скобка) или больше приоритета элемента S_j, находящегося в вершине стека, то добавить S_i в вершину стека и перейти к п.4; иначе перейти к п.5.
4. Если теперь элемент в вершине стека имеет приоритет, равный 1 (т.е. добавленный элемент S_i является закрывающей скобкой), то из стека удалить два верхних элемента (закрывающую и открывающую скобки) и затем перейти к п.1; иначе перейти кп.1.
5. Элемент (оператор) из вершины стека вытолкнуть в выходную строку и перейти к п.З.
6. Пункты 1 — 5 выполнять до тех пор, пока не встретится признак конца выражеия — символ '='. Тогда все элементы из стека вытолкнуть в выходную строку, затем занести туда символ “=”.

Рассмотрим порядок преобразования на примере строки 15*4+(25.2-3)^2=.
Шаг 1. Выделен операнд 15, заносим его в выходную строку. Выходная строка: 15, стек пуст.
Шаг 2. Выделен оператор '*', его приоритет больше приоритета пустого стека, помещаем в стек. Стек: *, выходная строка: 15.
Шаг 3. Выделен операнд 4, его в выходную строку. Выходная строка: 15 4, стек: *.
Шаг 4. Выделен оператор '+', его приоритет меньше приоритета '*' в вершине стека, поэтому '*' выталкиваем в выходную строку, а '+' заносим в стек. Выходная строка: 15 4*, стек: +.
Шаг 5. Выделена открывающая скобка с нулевым приоритетом, помещаем его в стек. Выходная строка: 15 4*, стек: + (.
Шаг 6. Выделен операнд 25, помещаем в выходную строку. Выходная строка: 15 4 * 25, стек: + (.
Шаг 7. Выделен оператор “/”, его приоритет выше приоритета '('. помещаем в стек. Строка: 15 4 * 25, стек: + ( /.
Шаг 8. Выделен операнд 2, его в строку: 15 4 * 25 2.
Шаг 9. Выделен оператор '-', его приоритет меньше приоритета “/” из вершины стека, поэтому ”/” — в строку, теперь приоритет '-' больше приоритета '(' и '-' заносим в стек. Выходная строка 15 4 * 25 2 /, стек: + ( -.
Шаг 10. Выделен операнд 3, его в строку: 15 4 + 25 2 / 3.
Шаг 11. Выделена закрывающая скобка ')', её приоритет меньше приоритета '-' из стека, поэтому '-' — в строку. Теперь приоритет ')' больше приоритета '('> помещаем ')' в стек, но так как его приоритет равен 1, то из стека удаляем два элемента: ')' и '(' без занесения их в выходную строку). Выходная строка: 15 4 * 25 2/3-, стек: +.
Шаг 12. Выделен оператор '^', его приоритет больше приоритета '+', '^' засылаем в стек: + ^, строка без изменения.
Шаг 13. Выделен операнд 2, его — в строку. 15 4*25 2/3-2.
Шаг 14. Выделен признак конца выражения '=', из стека выталкиваем в строку '^' и '+', затем в строку заносим '='. Выходная строка сформирована полностью: 15 4*25 2/3-2А+=, стек пуст.

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

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