Ответ в теме: Вычисление арифметического выражения (ПОЛИЗ)

      Комментарии к записи Ответ в теме: Вычисление арифметического выражения (ПОЛИЗ) отключены
#2532

ПОЛИЗ – очень удобный формат для вычисления выражений, он отличается лишь тем, что операторы располагаются после операндов, т.е. 3+5 будет записываться как 3 5 +
Алгоритм преобразования строки в польскую инверсную запись использует вспомогательный стек и формирует на выходе новую строку в формате ПОЛИЗ:

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

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