Преобразование инфикса в постфикс с использованием стека: методы и примеры

Я могу помочь вам с преобразованием инфикса в постфикс с помощью стека. Вот несколько способов добиться такого преобразования:

Метод 1: использование стека

  1. Инициализируйте пустой стек и пустую строку для хранения постфиксного выражения.
  2. Сканируйте инфиксное выражение слева направо.
  3. Если сканируемый элемент является операндом, добавьте его к постфиксному выражению.
  4. Если сканируемый элемент является оператором, выполните следующие действия:
    a. Если стек пуст или вершиной стека является открывающая скобка ‘(‘, поместите оператор в стек.
    b. Если сканируемый оператор имеет более высокий приоритет, чем вершина стека, поместите его в стек..
    c. Если сканируемый оператор имеет более низкий приоритет, чем верхняя часть стека, извлеките операторы из стека и добавьте их к постфиксному выражению до тех пор, пока не встретится оператор с более низким приоритетом или открывающаяся скобка. Затем нажмите сканируемый оператор. в стек.
    d. Если сканируемый оператор представляет собой закрывающую скобку ‘)’, извлеките операторы из стека и добавьте их к постфиксному выражению до тех пор, пока не встретится открывающая скобка. Удалите открывающую скобку из стека, но не добавляйте ее к постфиксному выражению.
  5. Повторяйте шаги 3–4, пока все элементы не будут отсканированы.
  6. Извлеките все оставшиеся операторы из стека и добавьте их в постфиксное выражение.
  7. Полученная строка является постфиксным выражением.

Метод 2: использование алгоритма маневровой станции

  1. Инициализируйте пустой стек и пустую строку для хранения постфиксного выражения.
  2. Сканируйте инфиксное выражение слева направо.
  3. Если сканируемый элемент является операндом, добавьте его к постфиксному выражению.
  4. Если сканируемый элемент является оператором, выполните следующие действия:
    a. Пока в верхней части стека находятся операторы с большим или равным приоритетом и оператор является левоассоциативным, извлеките операторы из стека и добавьте их в постфиксное выражение.
    b. Поместите отсканированный оператор в стек.
  5. Если сканируемый элемент представляет собой открывающую скобку «(», поместите ее в стек.
  6. Если сканируемый элемент представляет собой закрывающую скобку «)», извлеките операторы из стека и добавьте их к постфиксному выражению до тех пор, пока не встретите открывающую скобку. Удалите открывающую скобку из стека, но не добавляйте ее к постфиксному выражению.
  7. Повторяйте шаги 3–6, пока все элементы не будут отсканированы.
  8. Извлеките все оставшиеся операторы из стека и добавьте их в постфиксное выражение.
  9. Полученная строка является постфиксным выражением.