http://www.studfiles.ru/preview/1531803/
Алгоритм преобразования выражения из инфиксной записи в обратную польскую.
Для перевода выражения из инфиксной формы в постфиксную с учетом приоритетов операций и скобок существует простой алгоритм (Дейкстры). Алгоритм работает со стеком, в котором хранятся знаки операций. Сначала стек пуст. На вход алгоритму подается последовательность лексем (числа, скобки или знаки операций), представляющая некоторое арифметическое выражение, записанное в инфиксной форме. Результатом работы алгоритма является эквивалентное выражение в постфиксной форме. Вводятся приоритеты операций: открывающая скобка имеет приоритет 0, знаки + и – — приоритет 1 и знаки * и / — приоритет 2.
1. Пока не достигнут конец входной последовательности, читать очередную лексему и выполнять с ней следующие операции:
если прочитан операнд (число), записать его в выходную последовательность;
если прочитана открывающая скобка, положить её в стек;
если прочитана закрывающая скобка, вытолкнуть из стека в выходную последовательность всё до открывающей скобки, при этом сами скобки уничтожаются (удаляются из стека и в ответ не идут);
если прочитан знак операции, вытолкнуть из стека в выходную последовательность все операции с большим либо равным приоритетом, а прочитанную операцию положить в стек.
2. Если достигнут конец входной последовательности, вытолкнуть всё из стека в выходную последовательность и завершить работу.
Порядок операндов в выходной последовательности не отличается от порядка операндов в исходной последовательности. В выходной последовательности отсутствуют скобки.
Алгоритм вычисления значения выражения, представленного в обратной польской записи.
Для вычисления значения выражения, записанного в постфиксной форме, можно использовать описанный далее алгоритм. На вход подается последовательность лексем (числа или знаки операций), представляющая некоторое арифметическое выражение, записанное в постфиксной форме. Результатом работы алгоритма является значение этого выражения.
1. Пока не достигнут конец входной последовательности, читать очередную лексему и выполнять с ней следующие операции:
если прочитан операнд (число), положить его в стек;
если прочитан знак операции, вытолкнуть из стека два операнда и положить в стек результат применения прочитанной операции к этим операндам, взятым в обратном порядке.
2. Если достигнут конец входной последовательности, завершить работу. В стеке останется единственное число — значение исходного выражения.
