import java.util.Stack;
import java.util.EmptyStackException;
import java.util.Scanner;
import javax.swing.*;

class Arithmetic  
{
	Stack stk;
	String expression, postfix;
	int length;
	
	Arithmetic(String s)
	{
		expression = s;
		postfix = "";
		length = expression.length();
		stk = new Stack();
	}
	
	// Validate the expression - make sure parentheses are balanced
	boolean isBalance()
	{
		try
		{
			stk.clear();
			
			for(int i=0; i<length; i++)
			{
				char token = expression.charAt(i);
				
				if(token == Constants.LEFT_NORMAL)
				{
					stk.push(new Character(token));
				}
				else if(token == Constants.RIGHT_NORMAL)
				{
					stk.pop();
				}
			}
		}
		catch(EmptyStackException e)
		{
			return false;
		}
		
		if(stk.size() == 0)
		{
			return true;	
		}
		else
		{
			return false;
		}
		
	}
	
	// Convert expression to postfix notation
	boolean postfixExpression()
	{
		stk.clear();
		Scanner scan = new Scanner(expression);
		char current; 
		while (scan.hasNext())
		{
			String token = scan.next();
			if (isNumber(token))
				postfix = postfix + token + " ";	
			else 
			{
				current = token.charAt(0);
				if (isParentheses(current))
				{
					if(stk.empty() || current == Constants.LEFT_NORMAL)
					{
						stk.push(new Character(current));
					}
					else if (current == Constants.RIGHT_NORMAL)
					{
						try
						{
							Character ch = (Character)stk.pop();
							char top = ch.charValue();

							while (top != Constants.LEFT_NORMAL)
							{
								postfix = postfix + top + " ";
								ch = (Character)stk.pop();
								
								top = ch.charValue();	
							}
						}
						catch(EmptyStackException e)
						{
							JOptionPane.showMessageDialog(null, postfix);
							return false;
						}
					}
				}
				else if (isOperator(current))
				{
					if(stk.empty())
						stk.push(new Character(current));
					else
					{
						try
						{
							char top = (Character)stk.peek();
							boolean higher = hasHigherPrecedence(top, current);
							
							while(top != Constants.LEFT_NORMAL && higher)
							{								
								postfix = postfix + stk.pop() + " ";
								top = (Character)stk.peek();
							}
							stk.push(new Character(current));
						}
						catch(EmptyStackException e)
						{
							stk.push(new Character(current));
						}
					}
				}
			}
		}
		
		try
		{
			while(!stk.empty())
			{
				postfix = postfix + stk.pop() + " ";
			}
		}
		catch(EmptyStackException e)
		{
			
		}
		
		JOptionPane.showMessageDialog(null, postfix);
		return true;
	}						 

	boolean isNumber(String str)
	{
		try
		{
			Integer.parseInt(str);
			return true;
		}
		catch(NumberFormatException e)
		{
			return false;
		}
	}
		
	boolean isParentheses(char current)
	{
		if(current == Constants.LEFT_NORMAL || current == Constants.RIGHT_NORMAL)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	
	boolean isOperator(char ch)
	{
		switch(ch)
		{
			case Constants.ADD:
			case Constants.SUB:
			case Constants.MULT:
			case Constants.DIV:
				return true;
				
			default: //Not an operator
				return false;
		}
	}

	boolean hasHigherPrecedence(char top, char current)
	{
		int topPrecedence = 0;
		int currentPrecedence = 0;
		
		switch(top)
		{
			case Constants.ADD:
			case Constants.SUB:
				topPrecedence = 0;
				break;
			
			case Constants.MULT:
			case Constants.DIV:
				topPrecedence = 1;
				break;
		}
		
		switch(current)
		{
			case Constants.ADD:
			case Constants.SUB:
				currentPrecedence = 0;
				break;
			
			case Constants.MULT:
			case Constants.DIV:
				currentPrecedence = 1;
				break;
		}
		
		if(topPrecedence >= currentPrecedence)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	
	String getPostfix()
	{
		stk.clear();
		Scanner scan = new Scanner(postfix);
		
		while(scan.hasNext())
		{
			String token = scan.next();
			char currentChar = token.charAt(0);
			
			if(isNumber(token))
			{
				stk.push(token);
			}
			else if(isOperator(currentChar))
			{
				int t1 = 0, t2 = 0;
				
				try
				{
					t1 = Integer.parseInt((String)stk.pop());
					t2 = Integer.parseInt((String)stk.pop());
				}
				catch(EmptyStackException e)
				{
					return "The expression was invalid!";
				}
				
				int t3 = 0;
				switch(currentChar)
				{
					case Constants.ADD:
						t3 = t2 + t1;
						break;
						
					case Constants.SUB:
						t3 = t2 - t1;
						break;
						
					case Constants.MULT:
						t3 = t2 * t1;
						break;
						
					case Constants.DIV:
						t3 = t2 / t1;
						break;
				}
				
				stk.push(new Integer(t3).toString());
			}
		}
		
		if(stk.size() == 1)
		{
			return stk.pop().toString();
		}
		else
		{	
			String val = "";
			try
			{	
				while(true)
				{
					val = val + stk.pop().toString();
				}
			}
			catch(EmptyStackException e)
			{
				return val;
			}
		}
	}
}