Домашнее задание №7.

  1. Преобразовать арифметическое выражение в инфиксной записи в выражение в постфиксной. 

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

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

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

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