<ПРЕД Задача:
СЛЕД>
Задачу решили 110 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Из инфиксной в постфиксную

Time limit = 3 секунд(ы)

Дана инфиксная (обычная алгебраическая) запись арифметического выражения над целыми числами.

Язык этих выражений порождается следующей грамматикой:

 S ::= (S ('+' | '-'))? B
 B ::= (B ('*' | '/'))? A
 A ::= '-'? NUMBER
 	| '-'?  '(' S ')'
 NUMBER ::=  целое неотрицательное число не превосходящее 109 

При этом предполагается, что между отдельными элементами может стоять произвольное количество пробельных символов (пробел, символ табуляции, символ новой строки).

Все бинарные операции левоассоциативны.

Вход. Арифметическое выражения в инфиксной нотации, записанная, возможно, в нескольких строчках. Длина входа не превосходит 400000 символов.

Выход. Постфиксная форма выражения. Порядок чисел должен быть сохранён. Обратите внимание, что постфиксная запись определяется однозначно. Между соседними элементами должен стоять пробел. Унарный минус следует записывать в виде символа 'n'.

Вход#1
-1-2-3
Выход#1
1 n 2 - 3  -
Вход#2
-1-(2-3)
Выход#2
1 n 2 3 - -
Вход#3
1 + (3*4) *5  / 6/7
Выход#3
1 3 4 * 5 * 6 / 7 / +
Вход#4
100 + 1 - 
   1 / 34 + 1*2*3*4
Выход#4
100 1 + 1 34 / - 1 2 * 3 * 4 * +

Вход#5
1--2*4
Выход#5
1 2 n 4 * -

Автор:
Классическая задача. Описание и тесты -- Артем Ворожцов.

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 34.204.176.125