(495) 925-0049, ITShop интернет-магазин 229-0436, Учебный Центр 925-0049
  Главная страница Карта сайта Контакты
Поиск
Вход
Регистрация
Рассылки сайта
 
 
 
 
 

Алгоритмы и методы: Обратная польская запись (исходники)

Источник: trubetskoy1

Как правило арифметические выражения удобно преобразовывать в обратную польскую запись (ОПЗ), чтобы избавиться от скобок, содержащихся в выражении. Выражения, преобразованные в ОПЗ, можно вычислять последовательно, слева направо.

Существует два наиболее известных способа преобразования в ОПЗ. Рассмотрим коротко каждый из них:

1. Преобразование выражения в ОПЗ с использованием стека

Нам понадобится стек для переменных типа char, т.к. исходное выражение мы получаем в виде строки.

Рассматриваем поочередно каждый символ:
1. Если этот символ - число (или переменная), то просто помещаем его в выходную строку.
2. Если символ - знак операции (+, -, *, / ), то проверяем приоритет данной операции. Операции умножения и деления имеют наивысший приоритет (допустим он равен 3). Операции сложения и вычитания имеют меньший приоритет (равен 2). Наименьший приоритет (равен 1) имеет открывающая скобка.
Получив один из этих символов, мы должны проверить стек:

а) Если стек все еще пуст, или находящиеся в нем символы (а находится в нем могут только знаки операций и открывающая скобка) имеют меньший приоритет, чем приоритет текущего символа, то помещаем текущий символ в стек.
б) Если символ, находящийся на вершине стека имеет приоритет, больший или равный приоритету текущего символа, то извлекаем символы из стека в выходную строку до тех пор, пока выполняется это условие; затем переходим к пункту а).

3. Если текущий символ - открывающая скобка, то помещаем ее в стек.
4. Если текущий символ - закрывающая скобка, то извлекаем символы из стека в выходную строку до тех пор, пока не встретим в стеке открывающую скобку (т.е. символ с приоритетом, равным 1), которую следует просто уничтожить. Закрывающая скобка также уничтожается.

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

Рассмотрим алгоритм на примере простейшего выражения:
Дано выражение:
a + ( b - c ) * d

Рассмотрим поочередно все символы:

Символ
 
Действие
 
Состояние выходной строки после совершенного действия
 
Состояние стека после совершенного действия
a
 
'a' - переменная. Помещаем ее в выходную строку a
 
пуст
 
+
 
'+' - знак операции. Помещаем его в стек (поскольку стек пуст, приоритеты можно не проверять) a
 
+
 
(
 
'(' - открывающая скобка. Помещаем в стек. a
 
+ (
 
b
 
'b' - переменная. Помещаем ее в выходную строку a b
 
+ (
 
- '-' - знак операции, который имеет приоритет 2. Проверяем стек: на вершине находится символ '(', приоритет которого равен 1. Следовательно мы должны просто поместить текущий символ '-' в стек. a b
 
+ ( -
 
c
 
'c' - переменная. Помещаем ее в выходную строку a b c
 
+ ( -
)
 
')' - закрывающая скобка. Извлекаем из стека в выходную строку все символы, пока не встретим открывающую скобку. Затем уничтожаем обе скобки. a b c -
 
+
 
*
 
'*' - знак операции, который имеет приоритет 3. Проверяем стек: на вершине находится символ '+', приоритет которого равен 2, т.е. меньший, чем приоритет текущего символа '*'. Следовательно мы должны просто поместить текущий символ '*' в стек. a b c -
 
+ *
 
d
 
'd' - переменная. Помещаем ее в выходную строку a b c - d
 
+ *
 

Теперь вся входная строка разобрана, но в стеке еще остаются знаки операций, которые мы должны просто извлечь в выходную строку. Поскольку стек - это структура, организованная по принципу LIFO, сначала извлекается символ '*', затем символ '+'.
Итак, мы получили конечный результат:
a b c - d * +

Реализацию алгоритма можно скачать здесь.
Этот алгоритм также используется в программе Calc3, которая находится здесь (см. файл CPPNCalc.cpp).

2. Преобразование выражения в ОПЗ с помощью рекурсивного спуска
Реализация данного алгоритма представляет собой несколько функций, последовательно вызывающих друг друга.
Началом обработки выражения становится вызов функции begin(), которая обрабатывает сложение и вычитание (т.е. сохраняет их во временной переменной и помещает в выходную строку, когда к ней вернется управление после вызова функции mult_div()).
Функция begin() вызывает функцию mult_div(), обрабатывающую знаки деления и умножения (т.е. сохраняет их во временной переменной и помещает в выходную строку, когда к ней вернется управление после вызова функции symbol())..
Далее функция mult_div() вызывает функцию symbol(), обрабатывающую переменные (или числа) и скобки.
Если функция symbol() получает открывающую скобку, она вызывает функцию begin() (т.е. все начинается сначала) и ожидает закрывающей скобки, когда управление вновь возвращается к ней. Если она не дожидаестя закрывающей скобки, это означает, что в выражении содержится синтаксическая ошибка.
Если функция symbol() получает переменную, то помещает ее в выходную строку.

Рассмотрим работу этих функций на примере исходного выражения:
a + ( b - c ) * d

Передачу управления от одной функции к другой (т.е. вызов функции или возвращение управления вызвавшей функции) обозначим знаком -->

  1. Текущим символом является 'a'. Преобразование начинается с вызова функции begin(). Далее получаем цепочку вызовов begin() --> mult_div() --> symbol(). Функция symbol() помещает символ 'a' в выходную строку, заменяет текущий символ на '+' и возвращает управление. Состояние выходной строки: a
  2. Текущим символом является '+'. symbol() --> mult_div() --> begin(). Функция begin() запоминает текущий символ во временной переменной и заменяет его на '('. Состояние выходной строки: a
  3. Текущим символом является '('. begin() --> mult_div() --> symbol(). Функция symbol() заменяет текущий символ на 'b' и вызывает функцию begin(). Состояние выходной строки: a
  4. Текущим символом является 'b'. symbol()--> begin() --> mult_div() --> symbol(). Функция symbol() помещает символ 'b' в выходную строку, заменяет текущий символ на '-' и возвращает управление. Состояние выходной строки: a b
  5. Текущим символом является '-'. symbol() --> mult_div() --> begin(). Функция begin() запоминает текущий символ во временной переменной (поскольку эта переменная - локальная, это, конечно, не означает потерю символа '+', сохраненного ранее) и заменяет текущий символ на 'c'. Состояние выходной строки: a b
  6. Текущим символом является 'с'. begin() --> mult_div() --> symbol(). Функция symbol() помещает символ 'с' в выходную строку, заменяет текущий символ на ')' и возвращает управление. Состояние выходной строки: a b c
  7. Текущим символом является ')'. Поскольку закрывающую скобку ни одна функция не обрабатывает, функции поочередно возвращают управление, пока оно не возвратится к функции symbol(), которая обрабатывала открывающую скобку, т.е. цепочка будет такой: symbol() --> mult_div() --> begin(). (здесь функция begin() помещает сохраненный символ '-' в выходную строку) begin() --> symbol(). Далее функция symbol() заменяет текущий символ на '*' Состояние выходной строки: a b c -
  8. Текущим символом является '*'. symbol() --> mult_div() Функция mult_div() запоминает текущий символ во временной переменной и заменяет его на 'd' Состояние выходной строки: a b c -
  9. Текущим символом является 'd'. mult_div() --> symbol(). Функция symbol() помещает символ 'd' в выходную строку и возвращает управление. Состояние выходной строки: a b c - d
  10. Строка разобрана. Возвращение управления: symbol() --> mult_div() (здесь функция mult_div() помещает сохраненный символ '*' в выходную строку). Далее: mult_div() --> begin() (здесь функция begin() помещает сохраненный символ '+' в выходную строку) Состояние выходной строки: a b c - d * +

Реализация на С++ (для работы со строками и исключениями используются классы библиотеки VCL):


class TStr2PPN {
AnsiString instr, outstr; //input & output strings
char curc; //the current character
int iin; //the index of the input string

char nextChar(); //get the next character
void begin(); //handle plus & minus
void mult_div(); //handle multiplication & division
void symbol(); //handle characters & brackets

public:
TStr2PPN() { //constructor
iin = 1;
}

void convert(char *str); //convert to PPN
AnsiString get_outstr(); //get the output string
};


//get the next character
inline char TStr2PPN::nextChar() {
if(iin <= instr.Length()) return curc = instr[iin++];
return curc = '\0';
}

//get the output string
inline AnsiString TStr2PPN::get_outstr(){return outstr;}

//convert to PPN
void TStr2PPN::convert(char *str) {
try {
instr = str;
outstr.SetLength(0);
iin = 1;
nextChar();
//begin the convertation
begin();
if(iin != (instr.Length()+1) // curc != '\0') {
throw Exception("Syntax error");
}
if(!isalpha(instr[instr.Length()]) && instr[instr.Length()]!=')') {
throw Exception("Syntax error");
}
}
catch(...) {throw;}
}

//handle plus & minus
void TStr2PPN::begin() {
try {
mult_div();
while(curc=='+' // curc=='-') {
char temp = curc;
nextChar();
mult_div();
outstr += temp;
}
}
catch(...) {throw;}
}

//handle multiplication & division
void TStr2PPN::mult_div() {
try {
symbol();
while(curc=='*' // curc=='/') {
char temp = curc;
nextChar();
symbol();
outstr += temp;
}
}
catch(...) {throw;}
}

//handle characters
void TStr2PPN::symbol() {
try {
if(curc=='(') {
nextChar();
begin();
if(curc!=')') {
throw Exception("Error: wrong number of brackets");
}
else nextChar();
}
else
if(isalpha(curc)) {
outstr += curc;
nextChar();
}
else {throw Exception("Syntax error");}
}
catch(...) {throw;}
}

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

Рассмотрим этот алгоритм на примере выражения:
7 5 2 - 4 * +

Рассмотрим поочередно все символы:

Символ Действие Состояние стека после совершенного действия
7
 
'7' - число. Помещаем его в стек. 7
 
5
 
'5' - число. Помещаем его в стек. 7 5
 
2
 
'2' - число. Помещаем его в стек. 7 5 2
 
-
 
'-' - знак операции. Извлекаем из стека 2 верхних числа ( 5 и 2 ) и совершаем операцию 5 - 2 = 3, результат которой помещаем в стек 7 3
 
4
 
'4' - число. Помещаем его в стек. 7 3 4
 
*
 
'*' - знак операции. Извлекаем из стека 2 верхних числа ( 3 и 4 ) и совершаем операцию 3 * 4 = 12, результат которой помещаем в стек 7 12
 
+
 
'+' - знак операции. Извлекаем из стека 2 верхних числа ( 7 и 12 ) и совершаем операцию 7 + 12 = 19, результат которой помещаем в стек 19
 

Теперь строка разобрана и в стеке находится одно число 19, которое является результатом исходного выражения.

Реализация на С++:


int calculate(string str_in) {
Stack<int> val_stack; //стек
int n1, n2, res;

for(i = 0; i<str_in.length(); ++i) {
if(isNumber(str_out[i])) {
val_stack.push(str_out[i]);
}
else {
n2 = val_stack.pop();
n1 = val_stack.pop();
switch(str_out[i]) {
case '+': res = n1 + n2; break;
case '-': res = n1 - n2; break;
case '*': res = n1 * n2; break;
case '/': res = n1 / n2; break;
default: cout<<"Ошибка !\n";
}
val_stack.push(res);
}
}
return val_stack.pop();
}

Этот алгоритм также используется в программе Calc3, которая находится здесь (см. файл CPPNCalc.cpp).

Файлы для загрузки


 Распечатать »
 Правила публикации »
  Обсудить материал в конференции Micro Focus/Borland »
Обсудить материал в конференции Microsoft »
Обсудить материал в конференции Дизайн, графика, обработка изображений »
Написать редактору 
 Рекомендовать » Дата публикации: 21.10.2006 
 

Магазин программного обеспечения   WWW.ITSHOP.RU
Microsoft Windows Professional 10 Russian Upgrade Academic OLP 1 License No Level
Microsoft Skype for Business Server Standard CAL 2015 Sngl OLP 1License NoLevel DvcCAL
Microsoft Skype for Business 2016 Sngl OLP 1License NoLevel
Microsoft Project Russian License/Software Assurance Pack Academic OLP 1 License No Level
Microsoft Windows Professional 10, Электронный ключ
 
Другие предложения...
 
Курсы обучения   WWW.ITSHOP.RU
 
Другие предложения...
 
Магазин сертификационных экзаменов   WWW.ITSHOP.RU
 
Другие предложения...
 
3D Принтеры | 3D Печать   WWW.ITSHOP.RU
CubeX Trio
3D сканер SENSE
MakerBot Replicator 5th GEN
PICASO 3D Designer (Желтый)
MakerBot Replicator 2
 
Другие предложения...
 
Новости по теме
 
Рассылки Subscribe.ru
Информационные технологии: CASE, RAD, ERP, OLAP
Новости ITShop.ru - ПО, книги, документация, курсы обучения
Новые материалы
Программирование на Microsoft Access
Краткие описания программ и ссылки на них
Delphi - проблемы и решения
Программирование в AutoCAD
 
Рассылки Maillist.ru
Новости ITShop.ru - ПО, книги, документация, курсы обучения
 
Статьи по теме
 
Новинки каталога Download
 
Исходники
 
Документация
 
Обсуждения в форумах
Пишу программы на заказ профессионально (1944)
Пишу программы на заказ на языках Pascal (численные методы, списки, деревья, прерывания) под...
 
Разработка программ под заказ на Visual Basic/Delphi/PHP+MySQL/MS Access/MS SQL Server (46)
Доработка, модернизация и создание программ по заказу на Visual Basic/Visual...
 
Пишу программы на заказ для студентов (92)
Пишу для студентов на с, с++, паскаль в средах ms visual studio, qt, builder, borland c, delphi....
 
Помощь по MS Access (322)
Доброе время суток. Случайно оказался на этом сайте, искал статьи по OLAP. Вижу, что...
 
Как извлечь рисунки из файла Word (39)
Вообще-то есть еще способ - сделать в Word-е Copy рисунка, открыть Microsoft Photo Editor и там:...
 
 
 



    
rambler's top100 Rambler's Top100