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:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: NODEJS PERL 6 SCM chicken VB.net
Resource:-

hide comments
2015-01-26 07:51:21 Shabeeb Hashim
Fully parenthesized expression :),so no need to use infix to post fix conversion algorithm,it is simpler than that...
2015-01-18 12:39:15 Sachin verma
Well Rishab Both are differnet test case

Last edit: 2015-01-18 12:40:12
2015-01-18 07:55:55 Rishabh Agarwal
is this is a test case : (a + b^c)
or there will be parenthesis always i.e.
( a+ (b^c))
2015-01-14 20:07:22 Sachin verma
here +- got same priority and /* got same but higher than +-and( and ^ has highest priority
->must take case of case when stack is empty and you tring to get top or pop element
->no need to take care of case/problem with no () at all

Last edit: 2015-01-14 20:11:46
2015-01-08 07:14:32 Vinshi Vanvat
operating successfully on ideone but segmentation fault coming on spoj.. please help !!!
http://ideone.com/I005Vq
2015-01-05 15:21:36 karan
yepppppp :P :P pinku..

Last edit: 2015-01-13 19:42:55
2015-01-04 06:53:58 jaswin kaur
this problem was motivational
2015-01-03 18:50:39 Shubham
I am not able to implement the Shunting Yard Algorithm for this problem. Is there any other way/algo for this?
2014-12-30 10:47:24 arjun kesava
Do Note that, u r using pointers in this program and as there is only one operator between two operands, so there is no need to check priority.

Enjoy Coding.
2014-12-28 16:17:42 Avinash Raj
Done :) after a few attempts.

Last edit: 2014-12-29 19:15:19
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.