SPOJ ONP, Transform the Expression

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

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <list>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <bitset>
#include <algorithm>
#include <sstream>
using namespace std;
typedef long long int lli;
typedef long unsigned long llu;
#define mem_prep(varx) memset(varx,0,sizeof(varx))
#define pb push_back 
#define mp make_pair 
#define sz(v) ((int)v.size()) 
#define rep(i,a,n) for(int i=(a);i<(n);i++)  
#define repe(i,a,n)  for(int i=(a);i<=(n);i++)
#define forsz(i,a,v) rep(i,a,sz(v)) 
#define repsz(i,v) rep(i,0,sz(v)) 
#define vi vector<int>
#define vs vector<string>

istream* input; // pointer to input stream
string outp;
char op;

enum Token_value {
 NAME,  NUMBER,  END,
 PLUS='+', MINUS='-', MUL='*', DIV='/',
 PRINT=';', ASSIGN='=', LP='(',  RP=')',
 POW='^'
};

Token_value curr_tok = PRINT;
Token_value get_token()
{
  char ch;
  
  do {
    if(!input->get(ch)) return curr_tok = END;
  } while (ch!='\n' && isspace(ch));
  
  switch (ch) {
  case ';':
  case '\n':
    return curr_tok=PRINT;
  case '*':
  case '/':
  case '+':
  case '-':
  case '(':
  case ')':
  case '=':
  case '^':
    return curr_tok=Token_value(ch);
  default:   // NAME, NAME=, or error
    if (isalpha(ch)) {
      op = ch;
      return curr_tok=NAME;
    }
    return curr_tok=PRINT;
  }
}

void expr(bool); // cannot do without
void prim(bool get)  // handle primaries
{
  if (get) get_token();
  switch (curr_tok) {
  case NAME:
    {
      outp.pb(op);
      get_token();
      break;
    }
  case MINUS:
    {  // unary minus
      outp.pb('-');
      prim(true);
      break;
    }
  case LP:
    { 
      expr(true);
      get_token();      // eat ')'
      break;
    }
  }
}

void pow(bool get)
{
  prim(get);
  for(;;)
    switch(curr_tok){
    case POW:
      {
 prim(true);
 outp.pb('^');
 break;
      }
    default:
      return;
    }
}

void term(bool get) //mult and div
{
  pow(get);
  switch (curr_tok) {
  case MUL:
    {
      pow(true);
      outp.pb('*');
      break;
    }
  case DIV:
    {
      pow(true);
      outp.pb('/');
      break; 
    }
  default:
    return;
  }
}

void expr(bool get)  // add and subtract
{
  term(get);
  switch (curr_tok) {
  case PLUS:
    {
      term(true);
      outp.pb('+');
      break;
    }
  case MINUS:
    {
      term(true);
      outp.pb('-');
      break;
    }
    default:
      return;
  }
}

int main(int argc, char* argv[])
{
  input = &cin;

  while (*input) {
    get_token();
    if (curr_tok == END) break;
    if (curr_tok == PRINT) continue;
    expr(false);
    cout<<outp<<endl;
    outp.clear();
  }
  return 0;
}