Как преобразовать инфиксные выражения в постфиксные выражения

Обычная нотация, например A + B A + B A + B, эквивалентно инфиксной записи. Постфиксная нотация , также известная как обратная польская нотация, — это нотация, в которой операнды появляются перед своими операторами, например в выражении A B + AB + AB +. Достоинством постфиксной записи является однозначность последовательности операций. Фактически, круглые скобки в обозначении избыточны.

Преобразование из инфикса в постфикс

Стеки — идеальные структуры данных для преобразования инфиксов в постфиксные выражения. Мы просматриваем инфиксное выражение слева направо и принимаем решения в зависимости от того, является ли отсканированный символ (обычно называемый «токеном») операндом или оператором. Операнды помещаются в вывод, а операторы помещаются в стек; Итак, наше решение основано на приоритете оператора.

  1. Установите приоритет операций (типичный набор приоритетов показан на рисунке выше).
  2. Если токен является операндом, не помещайте его в стек. Вместо этого передайте его в вывод.
  3. Если токен является оператором или круглой скобкой, сделайте следующее:
  • Перед тем, как вы если оператор помещается в стек, вы должны извлекать стек, пока не найдете оператор с более низким приоритетом, чем текущий оператор. Выскакивающие элементы стека записываются для вывода.
  • Когда вы нашли подходящую позицию, сложите текущий оператор в стек.
  • Если ваш текущий токен является правой круглой скобкой, вставлять стек до тех пор, пока не появится первая левая скобка. Выведите все символы, кроме скобок.

Левая скобка в стеке удаляется только в случае обнаружения входящей правой скобки (в отличие от других операторов, таких как + — ? *, которые подчиняются только правилам приоритета).

  • После сканирования всего выражения вытолкните оставшуюся часть стека и запишите операторы из стека в выход.

Пример

В приведенном ниже примере мы рассмотрим, как преобразовать инфиксное выражение 4 2 + 5 ∗ ( 2 + 1 ) / 2 4 ^ 2 + 5 * (2 + 1)/2 4 2 + 5 * (2 + 1)/2 к постфиксу:

1 из 15

Оцените статью
nanomode.ru
Добавить комментарий