Sphere Online Judge

SPOJ Problem Set (classical)

4. Transform the Expression

Problem code: ONP


Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one RPN form (no expressions like a*b*c).

Input

t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]

Text grouped in [ ] does not appear in the input file.

Output

The expressions in RPN form, one per line.

Example

Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*

Added by:Micha≥ Ma≥afiejski
Date:2004-05-01
Time limit:5s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All except: NODEJS PERL 6
Resource:-

hide comments
2014-03-08 07:43:05 Shubham Aggarwal
it is infix to postfix
2014-03-05 14:08:17 Aviral
Easy Wheezy... just remember to empty the stack and adding to output before exiting...
2014-02-09 19:07:06 ANKIT KUMAR CODOPEDIAC
does "Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest)" mean that priority of "-" is higher than that of "+"?
2014-02-07 20:35:58 Sanat


Last edit: 2014-02-07 20:36:29
2014-01-28 10:02:35 Shatha Abu Hashem
Ugh .. I Just cannot find the algorithm .. it drives me crazy
2014-01-12 05:43:04 Anubhav Balodhi ;-D
Ac at first go. the very basic algorithm to convert infix to postfix. and the +,- have same priority, same goes for *,/ which is already...
Did I forget to mention, 50th ^_^


Last edit: 2014-02-05 08:13:42
2013-12-25 17:54:00 Bowen
"+, -, *, /, ^ (priority from the lowest to the highest)"
does - have higher precedence than + or are they the same? also with * and /?
2013-12-18 13:53:00 Ankit Jain
AC in one go!!!
2013-12-13 16:14:29 suryak
should we take input from standard IO?
2013-12-12 07:56:08 Duan Yichao
Write some more expressions yourself and try.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.