Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Алгоритм перевода инфиксного выражения в польскую форму записи

Стр 1 из 2Следующая ⇒


Читайте также:
  1. I Перепишите и письменно переведите на русский язык следующие предложения. Определите видо-временнную форму и залог сказуемого (см. образец).
  2. I. Внесение сведений в форму ДТС-1 при использовании метода определения таможенной стоимости по цене сделки с ввозимыми товарами
  3. I. Перепишите следующие предложения, определите в каждом из них видо-временную форму и залог глагола-сказуемого. Переведите предложения на русский язык.
  4. I. Перепишите следующие предложения, определите в каждом из них видо-временную форму и залог глагола-сказуемого. Переведите предложения на русский язык.
  5. I.I. Предмет фразеологии. Виды и признаки фразеологизмов. Особенности перевода фразеологизмов.
  6. II. Внесение сведений в форму ДТС-2 при использовании метода определения таможенной стоимости по цене сделки с идентичными товарами
  7. II. Перепишите и переведите предложения, поставив глагол в нужную форму.

Задача

Правильное арифметическое выражение в инфиксной форме записи записано в строке. Выражение может содержать: скобки (), знаки арифметических операций: +.-, *, / и цифры. Требуется перевести запись выражения в польскую форму (префиксную или постфиксную) и вычислить значение выражения.

Алгоритм перевода инфиксного выражения в польскую форму записи

Алгоритм основан на использовании числового стека. (“стек” — структура данных, в которой реализован принцип “последним пришел — первым вышел” (по-английски — “ L ast I n F irst O ut ”, или LIFO)).

Алгоритм перевода инфиксного выражения в префиксную форму записи (выражение помещается на левую сторону колодца)

1. Просматриваем инфиксную запись справа налево.

2. Если встречаем операнд, то копируем в префиксную запись

3. Если встречаем знак операции, то

Если стек пуст, то помещаем знак операции в стек

Иначе

Если приоритет последней операции в стеке <= приоритета текущей операции,

то помещаем знак операции в стек

Иначе

Записываем знаки операций из стека в префиксную запись до тех пор,

пока приоритет последней операции в стеке > приоритету текущей

операции.

Помещаем знак текущей операции в стек.

4. Если инфиксная запись не закончена, то переходим к 1., иначе к 5.

5. Записываем знаки операций из стека в префиксную запись до тех пор, пока стек не пуст.

Алгоритм перевода инфиксного выражения в постфиксную форму записи (помещаем выражение на правую сторону колодца)

1. Просматриваем инфиксную запись слева направо.

2. Если встречаем операнд, то копируем в постфиксную запись

3. Если встречаем знак операции, то

Если стек пуст, то помещаем знак операции в стек

Иначе

Если приоритет последней операции в стеке < приоритета текущей операции,

то помещаем знак операции в стек

Иначе

Записываем знаки операций из стека в постфиксную запись до тех пор,

пока приоритет последней операции в стеке >= приоритету текущей

операции.

Помещаем знак текущей операции в стек.

4. Если инфиксная запись не закончена, то переходим к 1., иначе к 5.

5. Записываем знаки операций из стека в постфиксную запись до тех пор, пока стек не пуст.

Дата добавления: 2015-07-10; просмотров: 1095 | Нарушение авторских прав

12Следующая ⇒



mybiblioteka.su - 2015-2024 год. (0.007 сек.)