Spoj00004,

## Problem:

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

## Solution:

Use the infix to postfix algorithms. Take the advantage of stack.

## Source Code:

```
//Mon Feb 21 19:09:43 CST 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, char* argv[]) {
//freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
int t;
cin >> t;
while (t--) {
string s1;
cin >> s1;
string stack = "";
string s2 = "";
for (int i = 0; i < s1.size(); i++) {
if (s1[i] == '+' || s1[i] == '-' || s1[i] == '*' || s1[i] == '/'
|| s1[i] == '(' || s1[i] == '^')
stack = s1[i] + stack;
else if (s1[i] == ')') {
while (stack.size() != 0 && stack[0] != '(') {
s2 += stack[0];
stack = stack.substr(1);
}
stack = stack.substr(1);
} else
s2 += s1[i];
}
cout << s2 << endl;
}
//fclose(stdin);
//fclose(stdout);
return 0;
}

```