Spoj_00004_Transform_the_Expression.cpp

Problem Links:

Spoj00004,

Problem:

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

---

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;
}