#include <iostream.h>

const int STACK_SIZE = 100;

int op_priority(char op);
void handle_operator(char next);

class STACK2
{
public:
   STACK2();    
   void push(char);
   char pop();
   char top();
   int top_p();
   bool is_empty();

private:
    char items[STACK_SIZE];
    int priority[STACK_SIZE];
    int size;
};

STACK2::STACK2() {
   size = 1;
   items[0] = '.';
   priority[0]=-1;
}



void STACK2::push(char item)
{
   items[size] = item;
   priority[size] = op_priority(item);
   if (item == '(')
      priority[size] = 1;
   size++;
}

char STACK2::pop()
{
   size--;
   return items[size];
}

char STACK2::top()
{
   return items[size-1];
}

int STACK2::top_p()
{
   return priority[size-1];
}

bool STACK2::is_empty()
{
   return (size==1);
}

STACK2 stack;

int main() 
{
char S[80];
cout << "Enter expression...Valid chars are alphabetic,:\n"; 
cout << "numeric, +, -, /, *, (, ), and ^              : ";
cin.getline(S,80,'\n');

int i=0;
while (i<strlen(S)) {
   char next_token = S[i];
   switch (next_token) {
      case ' ' : break;
      case '^':
      case '*':
      case '/':
      case '+':
      case '-':
      case '(':
      case ')': handle_operator(next_token); break;
      default: cout << next_token;
   }
   i++;
}
handle_operator('.');
cout << endl;
}

int op_priority(char op)
{
   switch (op) {
      case '^' : return 4; break;
      case '*':
      case '/': return 3; break;
      case '+':
      case '-': return 2; break;
      case '(': return 5; break;
      case ')': return 0; break;
      default: return -1; break;
   }
}

void handle_operator(char next)
{
if (next !='.') {
   int priority = op_priority(next);
   if (priority >= stack.top_p()) 
      stack.push(next);
   else {
      while (!stack.is_empty() && stack.top_p() >= priority) {
         char next_one = stack.pop();
         if (next_one != '(' && next_one != ')')
            cout << next_one;
      }
      stack.push(next);
   }
}
else 
 while (!stack.is_empty()) {
    char next_one = stack.pop();
    if (next_one != '(' && next_one != ')')
       cout << next_one;
    }
}