import java.util.*;
import java.math.*;
import java.io.*;
import java.lang.*;
 
 
public class Tokens{
 
    private int position=0;    //Postion  to put in array. Increases as the String is tokenized.
    private String [] Tokenized= new String[500];    //Tokenized version of array
    private Stack operand = new Stack();  //Operand Stack for conversion
    private static Stack output=new Stack(); //Output Stack for conversion. (Everything will be in here at end of conversion)
    private Stack reverse = new Stack(); //reverses the output into here
 
    //public Tokens()
    /********************************
    *Start of tokenize class. Once called it will use the Parse function
    *to tokenize the given String (ie. user input)*/
    //{
 
 
    //}
 
 
    public void Parse(String s){
        /****************************
        *Parse Function. Takes Input as string and tokenizes it to be able to use as a Token.
        ****************************/
        String temp=""; //Digits and operands are temporarily stored, seperatly in here.
        for (int i=0; i<s.length();i++){
            if(Character.isDigit(s.charAt(i))){
                temp+=s.substring(i,i+1);
            }
            else
            {
                if(temp != "")
                {
                    Tokenized[position]=temp;
                    position++;
                }
                temp="";
                switch (s.charAt(i)){
                    case '+':
                        temp="+";
                        break;
                    case '-':
                        temp="-";
                        break;
                    case '(':
                        temp="(";
                        break;
                    case ')':
                        temp=")";
                        break;
                    case '/':
                        temp="/";
                        break;
                    case '*':
                        if (s.charAt(i+1) == '*')
                        {
                            temp="^";
                            i++;
                        }
                        else{
                            temp="*";
                        }
                        break;
                    case ' ':
                        break;
                    default:
                        System.out.println("Incorrect format.");
                }
                if(temp != "")
                {
                    Tokenized[position]=temp;
                    position++;
                }
                temp = "";
            }
        }
    }
 
/*WORKS TO HERE NO PROBLEM!!!! */
 
    public int evaluate(String x){
        /*************************
        Evaluates the given sign.
        * +, - have same value:1
        * *, / have same value:2
        * ^ has value of: 3
        * otherwise it is value: 0
        *************************/
        if(x.equals("+") )
        {
            return 1;
        }
        else if(x.equals("-"))
        {
            return 1;
        }
        else if(x.equals("*"))
        {
            return 2;
        }
        else if (x.equals("/"))
        {
            return 2;
        }
        else if(x.equals("^"))
        {
            return 3;
        }
        else
        {
            return 4;
        }
 
    }
    public void Bracket()
    {
        String temp=((String)(operand.peek()));
        while(!((String)(operand.peek())).equals("("))
        {
            output.push(operand.pop());
        }
        operand.pop();
    }
    public void convert(String[] Tokenized){
        /****************************************************
        *takes the token created in Parse function and
        *converts it from Infix notation to postfix notion
        *Uses evaluate function to see what to do with signs
        * and puts it in 2 stacks operand and output
        *untill the end. at the end everything is in
        *stack output which will be returned
        ****************************************************/
        for (int j=0; j<position; j++)
        {
            if (Character.isDigit(Tokenized[j].charAt(0)))
            {
                output.push(Tokenized[j]);
            }
            else
            {
 
                if (!Tokenized[j].equals("("))
                {
                        if (operand.empty())
                        {
                            operand.push(Tokenized[j]);
                        }
                        else if (((String)(operand.peek())).equals("("))
                        {
                            operand.push(Tokenized[j]);
                        }
                        else if (Tokenized[j].equals(")"))
                        {
                            Bracket();
                        }
                        else if (Tokenized[j].equals("^"))
                        {
                            if (((String)(operand.peek())).equals("^"))
                            {
                                operand.push(Tokenized[j]);
                            }
                            else
                            {
                                int second=evaluate((String)(operand.peek()));
                                int first=evaluate(Tokenized[j]);
                                if (first > second)
                                {
                                    operand.push(Tokenized[j]);
                                }
                                else if (first == second)
                                {
                                    output.push(operand.pop());
                                    operand.push(Tokenized[j]);
                                }
                                else if (first < second)
                                {
                                output.push(operand.pop());
                                operand.push(Tokenized[j]);
                                }
                            }
                        }
                        else
                        {
                            int second=evaluate((String)(operand.peek()));
                            int first=evaluate(Tokenized[j]);
                            if (first > second)
                            {
                                operand.push(Tokenized[j]);
                            }
                            else if (first == second)
                            {
                                output.push(operand.pop());
                                operand.push(Tokenized[j]);
                            }
                            else if (first < second)
                            {
                                output.push(operand.pop());
                                operand.push(Tokenized[j]);
                            }
                        }
                }
                else if (Tokenized[j].equals("("))
                {
                    operand.push(Tokenized[j]);
                }
            }
        }
        while(!operand.empty())
        {
            output.push(operand.pop());
        }
        while (!output.empty())
        {
            reverse.push(output.pop());
        }
 
    }
 
    public double eval()
    /********************************
    *takes token output which is in postfix notation
    *Reads it and caluates it using the Switch/Case.
    ********************************/
    {
        Stack Tmp = new Stack();
        while ( !reverse.empty())
        {
            System.out.println("&&&&&&& "+ Tmp.peek());
            String x=(String)(reverse.peek());
            System.out.println(x);
 
            if (Character.isDigit(x.charAt(0)))
            {
                Tmp.push(reverse.pop());
            }
            else
            {
                String sign=(String)(reverse.pop());
                if (sign.equals("+"))
                {
                    double j=Double.parseDouble(((String)(Tmp.pop()+"")));
                    double y=Double.parseDouble(((String)(Tmp.pop()+"")));
                    double z;
                    z= (y + j);
                    Tmp.push(z);
                }
                else if ( sign.equals("-"))
                {
                    double a=Double.parseDouble(((String)(Tmp.pop()+"")));
                    double b=Double.parseDouble(((String)(Tmp.pop()+"")));
                    double c;
                    c= (b - a);
                    Tmp.push(c);
                }
                else if (sign.equals("*"))
                {
                    double first=Double.parseDouble(((String)(Tmp.pop()+"")));
                    double two=Double.parseDouble(((String)(Tmp.pop()+"")));
                    double three;
                    three= (two * first);
                    Tmp.push(three);
                }
                else if (sign.equals("/"))
                {
                    double d=Double.parseDouble(((String)(Tmp.pop()+"")));
                    double e=Double.parseDouble(((String)(Tmp.pop()+"")));
                    double f;
                    f= (e /d);
                    Tmp.push(f);
                }
                else if (sign.equals("^"))
                {
                    double g=Double.parseDouble(((String)(Tmp.pop()+"")));
                    double h=Double.parseDouble(((String)(Tmp.pop()+"")));
                    double i;
                    i= Math.pow(h,g);
                    Tmp.push(i);
                }
            }
        }
        Double o;
        o=Double.parseDouble(((String)(Tmp.pop()+"")));
        System.out.println("&&&&&      " + o);
        return o;
    }
    public static void main(String[] args)
    {
        double result;
        String store = " ";
        Tokens app = new Tokens();
        String temp;
        int k=0;
        System.out.print("c> ");
        Scanner scan=new Scanner(System.in);
        temp = scan.next();
        if (temp.equals("p"))
        {
            while (scan.hasNext())
            {
                store+=scan.next();
            }
        }
        else if (temp.equals("parse"))
        {
            while (scan.hasNext() && !(scan.next().equals("q")))
            {
                store+=scan.next();
            }
            app.Parse(store);
        }
        else if (temp.equals("convert"))
        {
            app.convert(app.Tokenized);
        }
    }
}

bool Equation::TakesPrecedence(char OperatorA, char OperatorB)
{
   if (OperatorA == '(')
      return false;
   else if (OperatorB == '(')
      return false;
   else if (OperatorB == ')')
      return true;
   else if ((OperatorA == '^') && (OperatorB == '^'))
      return false;
   else if (OperatorA == '^')
      return true;
   else if (OperatorB == '^')
      return false;
   else if ((OperatorA == '*') || (OperatorA == '/'))
      return true;
   else if ((OperatorB == '*') || (OperatorB == '/'))
      return false;
   else
      return true;   
}
 
void Equation::Convert(const string & Infix, string & Postfix)
{
   stack <char> OperatorStack;
   char TopSymbol, Symbol;
   int k;
 
   for (k = 0; k < Infix.size(); k++)
   {
      Symbol = Infix[k];
      if (IsOperand(Symbol))
         Postfix = Postfix + Symbol;
      else
      {
         while ((! OperatorStack.empty()) &&
            (TakesPrecedence(OperatorStack.top(), Symbol)))
            {
            TopSymbol = OperatorStack.top();
            OperatorStack.pop();
            Postfix = Postfix + TopSymbol;
            }
         if ((! OperatorStack.empty()) && (Symbol == ')'))
            OperatorStack.pop();   // discard matching (
         else
            OperatorStack.push(Symbol);
      }
   }
 
   while (! OperatorStack.empty())
   {
      TopSymbol = OperatorStack.top();
      OperatorStack.pop();
      Postfix = Postfix + TopSymbol;
   }
}