<PREV Problem:
NEXT>
Solved by 110 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Infix to postfix form

Time limit = 3 second(s)

Grammar of infix notation is the following:

 S ::= (S ('+' | '-'))? B
 B ::= (B ('*' | '/'))? A
 A ::= '-'? NUMBER
 	| '-'? '(' S ')'
 NUMBER ::=  nonnegative integer number less then 109 ;

Whitespace characters can be placed between any two elements ('\t', ' ', '\n').

All binary operands are left-associate.

Input. Several lines with infix form of arithmetic expression. It's length is less then 400000.

Output. Postfix expression. Tokens should be separated by space. Unary minus should be represented by letter 'n'.

Input#1
-1-2-3
Output#1
1 n 2 - 3  -
Input#2
-1-(2-3)
Output#2
1 n 2 3 - -
Input#3
1 + (3*4) *5  / 6/7
Output#3
1 3 4 * 5 * 6 / 7 / +
Input#4
100 + 1 - 
   1 / 34 + 1*2*3*4
Output#4
100 1 + 1 34 / - 1 2 * 3 * 4 * +

Input#5
1--2*4
Output#5
1 2 n 4 * -

Author:
Classic problem. Tests and description by Artem Voroztsov

<PREV | Problem set | Search related messages | NEXT>


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

SW soft NIX
ID = 54.224.18.114