#include <iostream>
#include "string"
#include "conio.h"
#include <cstdlib>
#include <algorithm>
#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
//template <class variable>
struct Node {
      int data;
      Node  *next;
      Node(){
       data=0;
       next=NULL;
      }
      Node(int x){
       data=x;
       next=NULL;
      }
    };
    //template <class variable>
    class Stack{
      Node *top=NULL;
      public:
      bool IsEmpty(){
        if(top==NULL)
            return true;
        else
            return false;
      }
      /*int isempty(){
        return top==0;
      }*/
      void Push(int x){
        Node *n=new Node (x);
        //n->data=x;
        if(IsEmpty())
            top=n;
        else{
            n->next=top;
            top=n;
        }
       }
      int Pop(){
       if(IsEmpty()==false){
        Node *t=top;
        int x=top->data;
        top=top->next;
        t->next=NULL;
        delete t;
        return x;
         }
        }
      void display(){
       if(IsEmpty()==false){
        Node *t=top;
        while(t->next!=NULL){
            cout<<t->data<<endl;
            t=t->next;
            }
          }
        }
      int Top(){
          if(!IsEmpty())
            return top->data;
          else
            exit(EXIT_FAILURE);

      }
      void Clear(){
        top=NULL;
      }
     };

//Function to return precedence of operators
int prec(char c)
{
	if(c == '*' || c == '/')
	return 2;
	else if(c == '+' || c == '-')
	return 1;
	else
	return -1;
}

// The main function to convert infix expression
//to postfix expression
void infixToPostfix(string s)
{
	Stack<char> st;
	st.Push('N');
	int l = s.length();
	string ns;
	for(int i = 0; i < l; i++)
	{
		// If the scanned character is an operand, add it to output string.
		if((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z'))
		ns+=s[i];

		// If the scanned character is an ‘(‘, push it to the stack.
		else if(s[i] == '(')

		st.Push('(');

		// If the scanned character is an ‘)’, pop and to output string from the stack
		// until an ‘(‘ is encountered.
		else if(s[i] == ')')
		{
			while(st.Top() != 'N' && st.Top() != '(')
			{
				char c = st.Top();
				st.Pop();
			ns += c;
			}
			if(st.Top() == '(')
			{
				char c = st.Top();
				st.Pop();
			}
		}

		//If an operator is scanned
		else{
			while(st.Top() != 'N' && prec(s[i]) <= prec(st.Top()))
			{
				char c = st.Top();
				st.Pop();
				ns += c;
			}
			st.Push(s[i]);
		}

	}
	//Pop all the remaining elements from the stack
	while(st.Top() != 'N')
	{
		char c = st.Top();
		st.Pop();
		ns += c;
	}

	cout << ns << endl;

}

//Driver program to test above functions
int main()
{
	string exp = "a+b*(c^d-e)^(f+g*h)-i";
	infixToPostfix(exp);
	return 0;
}