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