Назад

Методы программирования

Задание 2. Вычисления на стеке

Общая информация

Задание состоит из двух частей, первая из которых обязательна для выполнения, вторую необходимо выполнить для получения отличной оценки. Срок сдачи задания — 9 октября.

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

Теория

Говорят, что выражение записано в инфиксной форме, если знак операции (сложения, умножения, вычитания либо деления) стоит между своими аргументами, например, 5 + 7. Каждая операция имеет приоритет выполнения (сначала выполняются умножение и деление, затем сложение и вычитание). Для изменения приоритета выполнения операций используются круглые скобки.

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

Для перевода выражения из инфиксной формы в постфиксную с учетом приоритетов операций и скобок существует простой алгоритм (Дейкстры). Алгоритм работает со стеком, в котором хранятся знаки операций. Сначала стек пуст. На вход алгоритму подается последовательность лексем (числа, скобки или знаки операций), представляющая некоторое арифметическое выражение, записанное в инфиксной форме. Результатом работы алгоритма является эквивалентное выражение в постфиксной форме. Вводятся приоритеты операций: открывающая скобка имеет приоритет 0, знаки + и — приоритет 1 и знаки * и / — приоритет 2.

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

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

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

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

Ясно, что эти два алгоритма можно объединить, если в первом алгоритме вместо вывода в выходную последовательность передавать лексему сразу на вход второму алгоритму и обрабатывать «на лету» (придется поддерживать одновременно два стека).

Формулировка задания

Во входном файле input.txt в единственной строке находится арифметическое выражение, записанное в инфиксной форме (используются только целые положительные числа и четыре операции +, , *, /. В выходной файл output.txt записать значение этого выражения. Стеки реализовывать при помощи связанных списков (операции добавления в начало списка и удаления первого элемента, см. теорию по заданию 1.

Примеры

Ввод: input.txt
(1+2)*(3+4)
Вывод: output.txt
21

b. * Выполнение программы вычислений

Формулировка задания

Во входном файле input.txt находится программа, написанная на специальном языке программирования. В языке существуют два вида операторов: оператор присваивания VARIABLE=EXPRESSION, где VARIABLE — имя переменной, состоящее из букв и цифр, не начинающееся с цифры и длиной не более 5 символов, а EXPRESSION — выражение в инфиксной форме, содержащее целые числа, скобки, знаки операций (+, , *, /) и переменные и не содержащее пробелов. Значением любой переменной изначально считается 0, оператор присваивания изменяет значение переменной на значение выражения. Второй вид оператора — оператор вывода на экран: PRINT EXPRESSION, где PRINT — служебное слово, а EXPRESSION определяется так же, как и для оператора присваивания. Этот оператор выводит в файл output.txt значение выражения EXPRESSION и переводит строку.

Примеры

Ввод: input.txt
VAR1=5
VAR2=VAR1*(7+VAR3)
PRINT VAR1
PRINT VAR2+1
Вывод: output.txt
5
36