import java.util.Scanner;
import java.util.StringTokenizer;

public class Expressions2
{
  private static boolean isNumber(String s)
  {
    boolean retval = false;
    try
    {
      double value = Double.parseDouble(s);
      retval =true;
    }
    catch (Exception e)
    {
      retval = false;
    }
    return retval;
  }
 
  private static int getPrecedence(String token)
  {
    if (token.equals("+") || token.equals("-") )
      return 1;
    else if (token.equals("*") || token.equals("/") )
      return 2;
    else //not an operator
      return -1;
  }
     
    // convert given infixto postfix expression
    // using shunting yard algorithm
  public static Queue<String> infixToRpn(Queue<String> input)
  {
    Stack<String> opStack = new Stack<String>();
    Queue<String> outputQueue = new Queue<String>(); 

    while(!input.isEmpty())
    {
      String token = input.dequeue();
      
      if (isNumber(token)) //digits (later letters) into output queue
        outputQueue.enqueue(token);
      else if (token.equals("("))   //left paren to stack
      {
        opStack.push(token);
      }
          // If character is an ')'throw it away, then pop and stack
          // and enqueue it to outputQueue '(' is
          // encountered
      else if (token.equals(")"))
      {
        while (!opStack.isEmpty() && !opStack.peek().equals("("))
        {
          outputQueue.enqueue(opStack.pop());
        }
        if(opStack.isEmpty())
          throw new MalformedExpressionException("Illegal infix expression");
        opStack.pop(); // dispose of the '('
      }
      else //deal with operators
      {
        while(!opStack.isEmpty() && getPrecedence(token) <= getPrecedence(opStack.peek()))
        {
          outputQueue.enqueue(opStack.pop());
        }
        opStack.push(token);
      }
    }
        // pop all the remaining operators from
        // the stack and enqueue them to output
    while (!opStack.isEmpty()) 
    {
      if (opStack.peek().equals("("))
        throw new MalformedExpressionException ("Infix expression is invalid");
      outputQueue.enqueue(opStack.pop());
    }
    return outputQueue;
  }

 
  public static double stringToQueue(String line, Variables var)
  {
    Queue<String> input = new Queue<String>();
    Queue<String> output = new Queue<String>();
    Scanner kb = new Scanner(System.in);
    StringTokenizer st;

      
    st = new StringTokenizer(line, "+-*/() ", true);
    while(st.hasMoreTokens())
    {
      String token = st.nextToken();
      if(!token.equals(" "))
      {
        char first = token.charAt(0);
        if(first >= 'a' && first <= 'z' || first >= 'A' && first <= 'Z')
        {
          double val = var.getValue(token);
          input.enqueue("" + val);
        }
        else
        {
          input.enqueue(token);
        }
      }
    }
    output = infixToRpn(input);
    double answer = Expressions.RPNEvaluate(output);
    return answer;
  }
}