#include <bits/stdc++.h>
#include <ctype.h>
#include
using namespace std;
#define SIZE 100
class stackk {
char stackData[SIZE]; // holds the stack
int topOfStack;
string reversenotation; // index of top-of-stack
public:
stackk() { topOfStack = 0; }
void push(char ch)
{
if(topOfStack==SIZE) {
cout << “Stack is full\n”;
return;
}
stackData[topOfStack] = ch;
topOfStack++;
}
char top(){
return stackData[topOfStack];
}
int speciall(char ch){
if(ch==’+’ || ch==’-’||ch==’*’||ch==’^’){
return 1;
}
else{
return 0;
}
}
char pop(){
if(topOfStack==0) {
cout << “Stack is empty\n”;
return 0; // return null on empty stack
}
topOfStack–;
return stackData[topOfStack];
}
int priority(char ch){
switch(ch){
case ‘+’:
return 1;
break;
case '-':
return 2;
break;
case '*':
return 3;
break;
case '/':
return 4;
break;
case '^':
return 5;
break;
}
}
string reverspolish(string expr){
for(int i=0;i<expr.size();i++){
if(expr[i]=='('){
push(expr[i]);
}
if(isalpha(expr[i])){
reversenotation+=expr[i];
}
if(expr[i]==')'){
char current=pop();
while(current!='('){
reversenotation+=current;
current=pop();
}
}
if(speciall(expr[i])){
while(speciall(top())&&(priority(top())>priority(expr[i]))){
reversenotation+=pop();
}
push(expr[i]);
}
}
return reversenotation;
}
};
int main(){
stackk *obj;
int input;
string expr;
cin>>input;
obj=new stackk[input];
if(input<=100){
for(int i=0;i<input;i++){
cin>>expr;
cout<<obj[i].reverspolish(expr);
}
delete obj;
}
return 0;
}