RPN.cpp

#include <cstdio>
#include <stack>

using std::stack;
using std::scanf;
using std::printf;

unsigned int operatorPriority(char c) {
    switch (c) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        case '^': return 3;
        default:  return 0;
    }
}

bool isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/'  || c == '^';
}

bool hasHigherPriority(char a, char b) {
    return operatorPriority(a) > operatorPriority(b);
}

int main() {
	int n, size;
	scanf("%d", &n);
	
    char c;
    stack<char> stak;

	while(n--) {
		scanf("%d", &size);
        scanf("%c", &c);
        while(size--) {
            scanf("%c", &c);

            if (isOperator(c)) {
                printf(" ");
                while(!stak.empty() && stak.top() != '(' && hasHigherPriority(stak.top(), c)) {
                    printf("%c", stak.top());
                    stak.pop();
                }
                stak.push(c);
            } else if (c == '(') {
                stak.push('(');
            } else if (c == ')') {
                while(!stak.empty() && stak.top() !=  '(') {
                    printf("%c", stak.top());
                    stak.pop();
                }
                stak.pop();
            } else printf("%c", c);

        }
        while(!stak.empty()) {
            printf("%c", stak.top());
            stak.pop();
        }
    
        printf("\n");
	}
}