my c++ solution to codechef ONP - Transform the Expression

codechef ONP - Transform the Expression: http://www.codechef.com/problems/ONP/

Transform the Expression

All submissions for this problem are available.

Reverse Polish Notation (RPN) is a mathematical notation where every operator follows all of its operands. For instance, to add three and four, one would write "3 4 +" rather than "3 + 4". If there are multiple operations, the operator is given immediately after its second operand; so the expression written "3 − 4 + 5" would be written "3 4 − 5 +" first subtract 4 from 3, then add 5 to that.

Transform the algebraic expression with brackets into RPN form.

You can assume that for the test cases below only single letters will be used, brackets [] will not be used and each expression has only one RPN form (no expressions like a*b*c)

Input

The first line contains t, the number of test cases (less then 100).

Followed by t lines, containing an expression to be translated to RPN form, where the length of the expression is less then 400.

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+^*

---

Author:	admin
Tags	admin
Date Added:	1-12-2008
Time Limit:	5 sec
Source Limit:	50000 Bytes
Languages:	ADA, ASM, BASH, BF, C, C99 strict, CAML, CLPS, CPP 4.3.2, CPP 4.8.1, CPP11, CS2, D, ERL, FORT, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC

my c++ solution to codechef ONP - Transform the Expression: http://ideone.com/eY3A2o

#include <iostream>

#include <string>

#include <stack>

using namespace std;

int main() {

// your code goes here

int a, i;

string s;

stack <char> oper;

stack <char> extra;

cin>>a;

while(a--) {

cin>>s;

for(i=0; i<s.size(); i++) {

if(s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/' || s[i]=='^' || s[i]=='%') oper.push(s[i]);

else if(s[i]==')') {

cout<<oper.top();

oper.pop();

}

else if(s[i]=='(') extra.push(s[i]);

else cout<<s[i];

}

cout<<endl;

}

return 0;

}