Задание состоит из двух частей, первая из которых обязательна для выполнения, вторую необходимо выполнить для получения отличной оценки. Срок сдачи задания — 9 октября.
Говорят, что выражение записано в инфиксной форме, если знак операции (сложения, умножения,
вычитания либо деления) стоит между своими аргументами, например, 5 + 7.
Каждая операция имеет приоритет выполнения (сначала выполняются умножение и деление, затем сложение
и вычитание). Для изменения приоритета выполнения операций используются круглые скобки.
Вычислять значение выражения, записанного в инфиксной форме, неудобно. Проще сначала перевести его
в постфиксную, или обратную польскую запись, в которой знак операции записывается
после своих операндов, например, 5 7 +.
Для перевода выражения из инфиксной формы в постфиксную с учетом приоритетов операций и скобок
существует простой алгоритм (Дейкстры). Алгоритм работает со стеком, в котором хранятся знаки
операций. Сначала стек пуст. На вход алгоритму подается последовательность лексем (числа, скобки
или знаки операций), представляющая некоторое арифметическое выражение, записанное в инфиксной форме.
Результатом работы алгоритма является эквивалентное выражение в постфиксной
форме. Вводятся приоритеты операций: открывающая скобка имеет приоритет 0,
знаки + и –
— приоритет 1 и знаки * и / — приоритет 2.
Заметим, что порядок операндов в выходной последовательности не отличается от порядка операндов в исходной последовательности. В выходной последовательности отсутствуют скобки.
Для вычисления значения выражения, записанного в постфиксной форме, можно использовать описанный далее алгоритм. На вход подается последовательность лексем (числа или знаки операций), представляющая некоторое арифметическое выражение, записанное в постфиксной форме. Результатом работы алгоритма является значение этого выражения.
Ясно, что эти два алгоритма можно объединить, если в первом алгоритме вместо вывода в выходную последовательность передавать лексему сразу на вход второму алгоритму и обрабатывать «на лету» (придется поддерживать одновременно два стека).
Во входном файле input.txt в единственной строке находится арифметическое выражение,
записанное в инфиксной форме (используются только целые положительные числа и четыре операции
+, –, *, /. В выходной файл
output.txt записать значение этого выражения. Стеки реализовывать при помощи
связанных списков (операции добавления в начало списка и удаления первого элемента, см. теорию
по заданию 1.
Ввод: input.txt
(1+2)*(3+4)
|
Вывод: output.txt
21
|
Во входном файле input.txt находится программа, написанная на специальном языке программирования.
В языке существуют два вида операторов: оператор присваивания VARIABLE=EXPRESSION, где VARIABLE
— имя переменной, состоящее из букв и цифр, не начинающееся с цифры и длиной не более 5 символов, а EXPRESSION
— выражение в инфиксной форме, содержащее целые числа, скобки, знаки операций (+, –,
*, /) и переменные и не содержащее пробелов. Значением любой переменной изначально считается 0,
оператор присваивания изменяет значение переменной на значение выражения. Второй вид оператора — оператор
вывода на экран: PRINT EXPRESSION, где PRINT — служебное слово, а EXPRESSION
определяется так же, как и для оператора присваивания. Этот оператор выводит в файл output.txt значение
выражения EXPRESSION и переводит строку.
Ввод: input.txt
VAR1=5
|
Вывод: output.txt
5
|