обратная польская запись

Вопросы написания собственного программного кода (на любых языках)

Модератор: Olej

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

обратная польская запись

Непрочитанное сообщение Olej » 03 май 2017, 10:14

Обратная польская запись общеизвестна, всем кто изучал или просто интересовался программированием ... в частности, без этого никак в построении интерпретаторов, компиляторов ... да и вообще всяких калькуляторов.

А меня подвигла к этой теме совершенно частная история:

1. нужно помочь одному недорослю-мажору из МГУ в выполнении его курсовой работы ... а заодно слупить мне некоторую сумму в ассигнациях с родителя этого мажора за такое репетиторство
P.S. Мажоры! Я так вас люблю. :lol:
При любых первейших затруднениях - всем обращаться сюда! :lol: :oops:

2. обнаружил я, что, при множестве объяснений и обсуждений "в общем" - нет (или почти нет) в обозримом Интернет готовых образцов, примеров кода, которые можно бы взять за начальную точку...

3. написать это хотелось бы на C/C++, который в обработке символьных выражений совсем не так силён

4. меня интересовало бы сделать это не только для тривиального набора операций (пЫАнЭрского :lol: ) +, -, *, / ... % от силы ;-) , но и для операций, выходящих за пределы этих 2-х уровней приоритетов: а). логических <,>,==,!= ... , б). присвоения =

5. ну и, наконец, возможно это ещё кому пригодится и покажется полезным...

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: обратная польская запись

Непрочитанное сообщение Olej » 03 май 2017, 10:57

Olej писал(а): 5. ну и, наконец, возможно это ещё кому пригодится и покажется полезным...
В 1-м приближении это может выглядеть так:

Код: Выделить всё

[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
Это работающий вариант, но только для 4-х арифметических операций (с учётом приоритетов).
Вложения
ppn.tgz
(3.14 КБ) 123 скачивания

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: обратная польская запись

Непрочитанное сообщение Olej » 03 май 2017, 23:05

Olej писал(а): 2. обнаружил я, что, при множестве объяснений и обсуждений "в общем" - нет (или почти нет) в обозримом Интернет готовых образцов, примеров кода, которые можно бы взять за начальную точку...
Более-менее внятные (но не то, что меня интересовало) и просто любопытные для рассмотрения (особенно на разных языках программирования) реализации - здесь:
Обратная польская запись: примеры реализации
Разбор выражений. Обратная польская нотация

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: обратная польская запись

Непрочитанное сообщение Olej » 06 май 2017, 09:25

Olej писал(а): В 1-м приближении это может выглядеть так:
Некоторое примечание: для преобразования скобочного (инфиксного) выражения в обратную польскую запись (постфиксную) описаны (по крайней мере широко описаны, то что мне попадалось) 2 разных способа:

1. Метод рекурсивного спуска ... когда скобочные фрагменты выражения подаются рекурсивно на тот же обработчик...
Метод описан (плохо ... но более-менее внятно) здесь: Алгоритмы и методы: Обратная польская запись (исходники).

2. Метод сортировочной станции, предложенный Эдгаром Дейкстрой (метод с промежуточным стеком), описан очень подробно Алгоритм сортировочной станции и Обратная польская запись.

Подавляющее большинство реализаций использует метод Дейкстры, №2. И он кажется (мне кажется, IMHO) более общим ... по крайней мере, в части обработки в общем потоке символов функций с произвольным числом параметров. Например, заталкивая в постфиксную запись так:
sin( x ) => x sin()
write( x, y, z ) => x y z write()

Моя (показываемая пока) реализация как-раз использует метод рекурсивного спуска ... из-за его ... относительной лаконичности, простоты ... и моей персональной привязанности к рекурсивным алгоритмам :lol: .
Метод сортировочной станции Э.Дейкстры (в его общем виде) я оставил на потом.

И ещё один комментарий: зачем всё это?

1. Зачем это делать? Это составная часть написания интерпретатора некоторого C-подобного языка ... учебный проект, в котором меня попросили помочь, и который обязательно я опишу здесь рядом отдельной темой... , но это несколько попозже.

2. Зачем писать собственный код, когда есть (по Интернет) достаточно большое множество примеров? Так дело в том, что "множество примеров", в основном пересказывают перепевки одного и того же ограниченного варианта: операции +, -, *, / и ^ (степень). Меня же интересовало бы вовлечение в это число: а). сравнений <, > и т.д. б). присвоения = в). вызовов функций sin( x ), write( x, y, z ) ... и вложенных write( sin( x ), sin( y ), sin( z ) )...

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: обратная польская запись

Непрочитанное сообщение Olej » 06 май 2017, 09:41

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 » 06 май 2017, 09:48

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 гостей