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

Источник: 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).


Страница сайта http://test.interface.ru
Оригинал находится по адресу http://test.interface.ru/home.asp?artId=1492