обратная польская запись
Модератор: Olej
- Olej
- Писатель
- Сообщения: 21338
- Зарегистрирован: 24 сен 2011, 14:22
- Откуда: Харьков
- Контактная информация:
обратная польская запись
Обратная польская запись общеизвестна, всем кто изучал или просто интересовался программированием ... в частности, без этого никак в построении интерпретаторов, компиляторов ... да и вообще всяких калькуляторов.
А меня подвигла к этой теме совершенно частная история:
1. нужно помочь одному недорослю-мажору из МГУ в выполнении его курсовой работы ... а заодно слупить мне некоторую сумму в ассигнациях с родителя этого мажора за такое репетиторство
P.S. Мажоры! Я так вас люблю.
При любых первейших затруднениях - всем обращаться сюда!
2. обнаружил я, что, при множестве объяснений и обсуждений "в общем" - нет (или почти нет) в обозримом Интернет готовых образцов, примеров кода, которые можно бы взять за начальную точку...
3. написать это хотелось бы на C/C++, который в обработке символьных выражений совсем не так силён
4. меня интересовало бы сделать это не только для тривиального набора операций (пЫАнЭрского ) +, -, *, / ... % от силы , но и для операций, выходящих за пределы этих 2-х уровней приоритетов: а). логических <,>,==,!= ... , б). присвоения =
5. ну и, наконец, возможно это ещё кому пригодится и покажется полезным...
А меня подвигла к этой теме совершенно частная история:
1. нужно помочь одному недорослю-мажору из МГУ в выполнении его курсовой работы ... а заодно слупить мне некоторую сумму в ассигнациях с родителя этого мажора за такое репетиторство
P.S. Мажоры! Я так вас люблю.
При любых первейших затруднениях - всем обращаться сюда!
2. обнаружил я, что, при множестве объяснений и обсуждений "в общем" - нет (или почти нет) в обозримом Интернет готовых образцов, примеров кода, которые можно бы взять за начальную точку...
3. написать это хотелось бы на C/C++, который в обработке символьных выражений совсем не так силён
4. меня интересовало бы сделать это не только для тривиального набора операций (пЫАнЭрского ) +, -, *, / ... % от силы , но и для операций, выходящих за пределы этих 2-х уровней приоритетов: а). логических <,>,==,!= ... , б). присвоения =
5. ну и, наконец, возможно это ещё кому пригодится и покажется полезным...
- Olej
- Писатель
- Сообщения: 21338
- Зарегистрирован: 24 сен 2011, 14:22
- Откуда: Харьков
- Контактная информация:
Re: обратная польская запись
В 1-м приближении это может выглядеть так:Olej писал(а): 5. ну и, наконец, возможно это ещё кому пригодится и покажется полезным...
Код: Выделить всё
[olej@dell ppn]$ ./ppntest
Вводите выражения:
> (aa - b) * ( d * (aa / (x1 + x2) )
(aa - b) * ( d * (aa / (x1 + x2) ) => синтаксис - баланс скобок :
(aa - b) * ( d * (aa / (x1 + x2) )
^
> (aa - b) * ( d * (aa / (x1 + x2) ))
(aa - b) * ( d * (aa / (x1 + x2) )) => aa b - d aa x1 x2 + / * *
> ^C
- Вложения
-
- ppn.tgz
- (3.14 КБ) 123 скачивания
- Olej
- Писатель
- Сообщения: 21338
- Зарегистрирован: 24 сен 2011, 14:22
- Откуда: Харьков
- Контактная информация:
Re: обратная польская запись
Более-менее внятные (но не то, что меня интересовало) и просто любопытные для рассмотрения (особенно на разных языках программирования) реализации - здесь:Olej писал(а): 2. обнаружил я, что, при множестве объяснений и обсуждений "в общем" - нет (или почти нет) в обозримом Интернет готовых образцов, примеров кода, которые можно бы взять за начальную точку...
Обратная польская запись: примеры реализации
Разбор выражений. Обратная польская нотация
- Olej
- Писатель
- Сообщения: 21338
- Зарегистрирован: 24 сен 2011, 14:22
- Откуда: Харьков
- Контактная информация:
Re: обратная польская запись
Некоторое примечание: для преобразования скобочного (инфиксного) выражения в обратную польскую запись (постфиксную) описаны (по крайней мере широко описаны, то что мне попадалось) 2 разных способа:Olej писал(а): В 1-м приближении это может выглядеть так:
1. Метод рекурсивного спуска ... когда скобочные фрагменты выражения подаются рекурсивно на тот же обработчик...
Метод описан (плохо ... но более-менее внятно) здесь: Алгоритмы и методы: Обратная польская запись (исходники).
2. Метод сортировочной станции, предложенный Эдгаром Дейкстрой (метод с промежуточным стеком), описан очень подробно Алгоритм сортировочной станции и Обратная польская запись.
Подавляющее большинство реализаций использует метод Дейкстры, №2. И он кажется (мне кажется, IMHO) более общим ... по крайней мере, в части обработки в общем потоке символов функций с произвольным числом параметров. Например, заталкивая в постфиксную запись так:
sin( x ) => x sin()
write( x, y, z ) => x y z write()
Моя (показываемая пока) реализация как-раз использует метод рекурсивного спуска ... из-за его ... относительной лаконичности, простоты ... и моей персональной привязанности к рекурсивным алгоритмам .
Метод сортировочной станции Э.Дейкстры (в его общем виде) я оставил на потом.
И ещё один комментарий: зачем всё это?
1. Зачем это делать? Это составная часть написания интерпретатора некоторого C-подобного языка ... учебный проект, в котором меня попросили помочь, и который обязательно я опишу здесь рядом отдельной темой... , но это несколько попозже.
2. Зачем писать собственный код, когда есть (по Интернет) достаточно большое множество примеров? Так дело в том, что "множество примеров", в основном пересказывают перепевки одного и того же ограниченного варианта: операции +, -, *, / и ^ (степень). Меня же интересовало бы вовлечение в это число: а). сравнений <, > и т.д. б). присвоения = в). вызовов функций sin( x ), write( x, y, z ) ... и вложенных write( sin( x ), sin( y ), sin( z ) )...
- Olej
- Писатель
- Сообщения: 21338
- Зарегистрирован: 24 сен 2011, 14:22
- Откуда: Харьков
- Контактная информация:
Re: обратная польская запись
Следующая реализация.Olej писал(а): 1. Метод рекурсивного спуска ...
Теперь она покрывает операции: + и -, * и /, ^ степень и сравнения < и >.
Операции (пока) ограничены только односимвольными, но это исключительно для простоты и наглядности - теперь ничто не мешает, по аналогии, добавить операции, например == и != ...
Второе существенное расширение: в тестовую программу теперь добавлена исполняющая система стековой машины, пытающаяся вычислить полученное постфиксное выражение, если входящие в него операнды являются числами. Вычислитель имеет примерно такой вид:
Код: Выделить всё
typedef long (*op_func)( long, long );
class opers { // реализуемые вычислителем операции
static map< string, op_func > ops;
public:
op_func find( string& s ) { // поиск операции по её изображению
try { return ops.at( s ); }
catch(...) { return NULL; } // исключение если операция не найдена
}
} aops;
map< string, op_func > opers::ops = {
{ "<", []( long o1, long o2 )-> long { return o1 < o2 ? 1 : 0; } },
{ ">", []( long o1, long o2 )-> long { return o1 > o2 ? 1 : 0; } },
{ "+", []( long o1, long o2 )-> long { return o1 + o2; } },
{ "-", []( long o1, long o2 )-> long { return o1 - o2; } },
{ "*", []( long o1, long o2 )-> long { return o1 * o2; } },
{ "/", []( long o1, long o2 )-> long { return o1 / o2; } },
{ "^", []( long o1, long o2 )-> long {
if( 0 == o2 ) return 1;
long res = o1;
while( o2-- > 1 ) res *= o1;
return res; }
}
};
long exec( vector<string>& p ) { // вычисление выражения (если числовое)
stack<long> stak;
for( string &o : p ) {
op_func eval = aops.find( o );
if( eval ) { // операция
if( stak.size() < 2 )
throw syn_exception( "пустой стек операндов" );
long o1, o2;
o2 = stak.top();
stak.pop();
o1 = stak.top();
stak.pop();
stak.push( eval( o1, o2 ) );
}
else { // операнд
try {
long n = stol( o );
stak.push( n );
}
catch(...) {
throw syn_exception( "не известный символ: " + o );
}
}
}
if( stak.size() != 1 )
throw syn_exception( "не освобождённый стек операндов" );
return stak.top();
}
А вызывается преобразование в постфиксную запись + последующее вычисление - как-то так:
Код: Выделить всё
...
str2ppn pp;
try { // преобразовать
vector<string> v = pp.convert( line );
cout << pp;
}
catch( syn_exception& e ) { // синтаксическая ошибка
return inp;
}
try {
cout << " = " << exec( pp.outstr ) << endl;
}
catch( syn_exception& e ) {
cout << endl << string( (const char*)e ) << endl;
}
return inp;
...
Код: Выделить всё
class syn_exception : exception {
string what;
public:
syn_exception( const string& s ) : what( s ) {}
operator const char*() { return what.c_str(); }
};
- Вложения
-
- ppn.2.tgz
- (5.25 КБ) 132 скачивания
- Olej
- Писатель
- Сообщения: 21338
- Зарегистрирован: 24 сен 2011, 14:22
- Откуда: Харьков
- Контактная информация:
Re: обратная польская запись
А сделано это так потому, что, как оказалось, при чуть более-менее сложных скобочных выражениях для человека становится крайне сложно контролировать точное соответствие полученную из него постфиксную запись. Но зато человеку крайне просто вычислить численный результат привычной инфиксной, скобочной записи и сравнить его с результатом, вычисленным по постфиксному выражению стековой машиной.Olej писал(а):Второе существенное расширение: в тестовую программу теперь добавлена исполняющая система стековой машины, пытающаяся вычислить полученное постфиксное выражение, если входящие в него операнды являются числами.
Выглядит это примерно так:
Код: Выделить всё
[olej@dell ppn]$ ./ppntest
Вводите выражения:
> 2 ^ 3
2 ^ 3 => 2 3 ^ = 8
> 1 + (8*2+1)/(1-5)^2
1 + (8*2+1)/(1-5)^2 => 1 8 2 * 1 + 1 5 - 2 ^ / + = 2
> (1-5)^3
(1-5)^3 => 1 5 - 3 ^ = -64
> 3 + 4 * 2 / (1 - 5)^2
3 + 4 * 2 / (1 - 5)^2 => 3 4 2 * 1 5 - 2 ^ / + = 3
> ^C
Код: Выделить всё
[olej@dell ppn]$ ./ppntest
Вводите выражения:
> 3 + 4 * 2 / (1 - 5)^2
3 + 4 * 2 / (1 - 5)^2 => 3 4 2 * 1 5 - 2 ^ / + = 3
> 1 + (8*2+1)/(1-5)^2
1 + (8*2+1)/(1-5)^2 => 1 8 2 * 1 + 1 5 - 2 ^ / + = 2
> a > b
a > b => a b >
не известный символ: a
> ( a + 5 ) < b / 3
( a + 5 ) < b / 3 => a 5 + b 3 / <
не известный символ: a
> ^C
Код: Выделить всё
[olej@dell ppn]$ ./ppntest
Вводите выражения:
> (3 + 2 ) > ( 7 / 2 )
(3 + 2 ) > ( 7 / 2 ) => 3 2 + 7 2 / > = 1
> 2^3 < 5 + 6
2^3 < 5 + 6 => 2 3 ^ 5 6 + < = 1
> 2 ^ 3 > 10 - 3
2 ^ 3 > 10 - 3 => 2 3 ^ 10 3 - > = 1
> 2 ^ 3 > 10 - 1
2 ^ 3 > 10 - 1 => 2 3 ^ 10 1 - > = 0
> ^C
Кто сейчас на конференции
Сейчас этот форум просматривают: нет зарегистрированных пользователей и 13 гостей