seocod.ru
http://seocod.ru/forum/

обратная польская запись
http://seocod.ru/forum/viewtopic.php?f=31&t=5261
Страница 1 из 1

Автор:  Olej [ 03 май 2017, 10:14 ]
Заголовок сообщения:  обратная польская запись

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

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

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

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

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

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

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

Автор:  Olej [ 03 май 2017, 10:57 ]
Заголовок сообщения:  Re: обратная польская запись

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 КБ]
Скачиваний: 23

Автор:  Olej [ 03 май 2017, 23:05 ]
Заголовок сообщения:  Re: обратная польская запись

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

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

Автор:  Olej [ 06 май 2017, 09:25 ]
Заголовок сообщения:  Re: обратная польская запись

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 [ 06 май 2017, 09:41 ]
Заголовок сообщения:  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 КБ]
Скачиваний: 27

Автор:  Olej [ 06 май 2017, 09:48 ]
Заголовок сообщения:  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

Страница 1 из 1 Часовой пояс: UTC + 3 часа
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/