import java.lang.*;
import java.util.*;
import java.util.regex.*;

//********************************************************************
//  ListNode.java       Author: AP Committee, comments added by
//                              Lewis/Loftus/Cocking
//
//  A node in a linked list.
//********************************************************************

class ListNode
{
   private Object value;
   private ListNode next;

   //-----------------------------------------------------------------
   //  Initializes this node.
   //-----------------------------------------------------------------
   public ListNode (Object initValue, ListNode initNext)
   {
      value = initValue;
      next = initNext;
   }

   //-----------------------------------------------------------------
   //  Returns the value of this node.
   //-----------------------------------------------------------------
   public Object getValue ()
   {
      return value;
   }

   //-----------------------------------------------------------------
   //  Returns the next reference in this node.
   //-----------------------------------------------------------------
   public ListNode getNext ()
   {
      return next;
   }

   //-----------------------------------------------------------------
   //  Sets the value of this node.
   //-----------------------------------------------------------------
   public void setValue (Object theNewValue)
   {
      value = theNewValue;
   }

   //-----------------------------------------------------------------
   //  Sets the next reference in this node.
   //-----------------------------------------------------------------
   public void setNext (ListNode theNewNext)
   {
      next = theNewNext;
   }
}

//********************************************************************
//  LinkedList.java
//********************************************************************

class LinkedList
{
	private ListNode head;

	public LinkedList() { head = null; }

	public void addToHead(Object o)
	{
		head = new ListNode(o, head);
	}

	public Object removeFromHead()
	{
		if(head==null) return null;

		Object o = head.getValue();

		head = head.getNext();
		return o;
	}

	public Object head()
	{
		return (head==null)?null:head.getValue();
	}

	public Object removeFromTail()
	{
		Object o;

		boolean headless = (head == null);

		if(headless || head.getNext() == null)
		{
			if(!headless)
			{
				o = head.getValue();

				head = null;
				return o;
			}
			return null;
		}

		ListNode n = head;
		while(n.getNext() != null && n.getNext().getNext() != null) { n = n.getNext(); }

		o = n.getNext().getValue();

		n.setNext(null);
		return o;
	}

	public Object tail()
	{
		Object o;

		boolean headless = (head == null);

		if(headless || head.getNext() == null)
		{
			return headless?null:head.getValue();
		}

		ListNode n = head;
		while(n.getNext() != null) { n = n.getNext(); }

		return n.getValue();
	}

	public boolean isEmpty() { return (head == null); }
}

//********************************************************************
//  Queue.java
//********************************************************************

class Queue
{
	protected LinkedList list;

	//-----------------------------------------------------------------
	//  Initializes the Queue.
	//-----------------------------------------------------------------
	public Queue() { list = new LinkedList(); }
	
	//-----------------------------------------------------------------
	//  Returns true if queue is empty.
	//-----------------------------------------------------------------
	public boolean isEmpty() { return list.isEmpty(); }
	
	//-----------------------------------------------------------------
	//  Adds an object to the queue.
	//-----------------------------------------------------------------
	public void push(Object o) { list.addToHead(o); }
	
	//-----------------------------------------------------------------
	//  Removes an object from the queue.
	//-----------------------------------------------------------------
	public Object pop() { return list.removeFromTail(); }

	//-----------------------------------------------------------------
	//  Returns the frontmost object.
	//-----------------------------------------------------------------
	public Object top() { return list.tail(); }
}

//********************************************************************
//  Stack.java
//
//  Stack extends Queue because they only differ by one function.
//  Queue could have just as easily been based on Stack.
//********************************************************************

class Stack extends Queue
{
	//-----------------------------------------------------------------
	//  Initializes the Stack.
	//-----------------------------------------------------------------
	public Stack() { super(); }

	//-----------------------------------------------------------------
	//  Removes an object from the stack.
	//-----------------------------------------------------------------
	public Object pop() { return list.removeFromHead(); }
}

//********************************************************************
//  my_prefixExpression.java
//********************************************************************

public class my_prefixExpression
{
	public static void main(String args[])
	{
		Queue queue = new Queue();

		System.out.println("Enter a prefix expression with format similar to \'(+ 1 (* 2 (% 3 4)))\':");
		Scanner in = new Scanner(System.in);
		String string = in.nextLine();
		in.close();

		System.out.println("Value:");

		if(enqueuePrefix(queue, string))
		{
			System.out.println(evaluatePrefix(queue));
		}
		else
		{
			System.out.println("Invalid");
		}
	}
	public static double dmod(double a, double b)
	{
		double c = Math.IEEEremainder(a, b);
		return (c < 0.0)?(c+b):(c);
	}

	//-----------------------------------------------------------------
	//  Traverses & enqueue input using regular expressions.
	//
	//  Note that this enqueuePrefix handles all syntactical errors.
	//-----------------------------------------------------------------
	private static boolean enqueuePrefix(Queue queue, String string)
	{
		// An operation is in the format (operator a b)
		// where a and b can be operations or numbers
		// The following is the regular expression for (operator a b)
		Pattern op = Pattern.compile("^(\\(([+-/*%]) ([\\d]+|\\(.+\\)) ([\\d]+|\\(.+\\))\\))$");

		// The following is the regular expression for an integer
		Pattern num = Pattern.compile("^[\\d]+$");

		Matcher match_op = op.matcher(string);
		Matcher match_num = num.matcher(string);

		if(match_op.matches()) // Input matched operation format
		{
			// Order the pieces backwards

			boolean r = enqueuePrefix(queue, match_op.group(4))
				&& enqueuePrefix(queue, match_op.group(3));

			// Operations are stored as String
			// because char does not extend Object
			queue.push(match_op.group(2));

			return r;
		}
		else if(match_num.matches()) // Input matched number format
		{
			queue.push(new Double(string));
			return true;
		}
		return false;
	}

	//-----------------------------------------------------------------
	//  Evaluates enqueued prefix expression
	//
	//  Note that this enqueuePrefix handles all syntactical errors.
	//-----------------------------------------------------------------
	private static double evaluatePrefix(Queue queue)
	{
		Stack stack = new Stack();

		Double a, b;

		// Transfer to stack and evaluate all objects in the queue
		while(!queue.isEmpty())
		{
			Object o = queue.pop();
			char op = o.toString().charAt(0);
			if("+-*/%".indexOf(op,0)>-1) // Check for operation
			{
				a = (Double)stack.pop();
				b = (Double)stack.pop();

				// Extract char operation from String and evaluate
				switch(op)
				{
					case '+': stack.push(new Double(a + b)); break;
					case '-': stack.push(new Double(a - b)); break;
					case '*': stack.push(new Double(a * b)); break;
					case '/': stack.push(new Double(a / b)); break;
					case '%': stack.push(new Double(dmod(a, b))); break;
				}
			}
			else
			{
				stack.push(o);
			}
		}

		return ((Double)stack.pop()).doubleValue();
	}
}