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

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

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

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

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