N2O

#include <iostream>
#include <sstream>
#include <stack>
#include <ctype.h>

using namespace std;

string Spaced(string userString);

string Spaced(string userString)
{
    string spacedString = "";
    int i1 = 0;
    int i2 = 0;

    for (unsigned int i = 0; i < userString.length(); i++)
    {
        string s1 (1, userString[i]);
        string s2 (1, userString[i + 1]);
        i1 = userString[i];
        i2 = userString[i + 1];

        if (!isdigit(i1) || !isdigit(i2))
        {
            spacedString += s1 + " ";
        } else
        {
            spacedString += s1;
        }
    }

    return spacedString;
}

string infixToPostfix(const string& infix) {
    const string ops = "-+/*^";
    stringstream ss;
    stack<int> s;

    stringstream input(infix);
    string token;
    while (getline(input, token, ' ')) {
        if (token.empty()) {
            continue;
        }

        char c = token[0];
        size_t idx = ops.find(c);

        if (idx != string::npos) {
            while (!s.empty()) {
                int prec2 = s.top() / 2;
                int prec1 = idx / 2;
                if (prec2 > prec1 || (prec2 == prec1 && c != '^')) {
                    ss << ops[s.top()] << ' ';
                    s.pop();
                } else break;
            }
            s.push(idx);
        } else if (c == '(') {
            s.push(-2);
        } else if (c == ')') {
            while (s.top() != -2) {
                ss << ops[s.top()] << ' ';
                s.pop();
            }
            s.pop();
        } else {
            ss << token << ' ';
        }
    }

    while (!s.empty()) {
        ss << ops[s.top()] << ' ';
        s.pop();
    }

    return ss.str();
}

int main() {

    int dump;
    int t;
    string userString;
    cin >> t;

    string tab[t];

    for(int i=0; i<t; i++){
        cin >> dump;
        cin >> tab[i];
    }

    for(int j=0; j<t; j++){
        userString = tab[j];
        string infix = Spaced(userString);
        cout << infixToPostfix(infix) << '\n';
    }

    return 0;
}