calculate.java

超级多项式计算器

import java.util.Stack;
import java.util.Vector;
import java.util.StringTokenizer;

/**Class Calculate<br/>
  *This class is to complete the calculate task.
  *It contains a static method -- calculateTerms() <br/>
  *This method can calculate any legal polynomial
  *and return the result.
  *@author zhlmmc
  *@version 1.0
  */

public final class Calculate
{
	private static int pos = 0;//pos is the index of the current character of the String	

    /**method calculateTerms
	  *to calculate the expression contians numbers and terms.
	  *Receive any valued expression and this method will return a number or a alia-polynomial as the result.
	  *@param s to be calculated expression
	  *@return Vector which elements are the terms
	  */
	public static Vector calculateTerms(String s)
	{
		
		/**s1 to store the operate number
		  *s2 to store the operator
		  *tempV to store the current fact before it is pushed to the stack
		  */
		Stack s1 = new Stack();
		Stack s2 = new Stack();
		Vector tempV = new Vector();
		
		//'('in the stack has the least precedence,so the first operate can be pushed in the stack
		s2.push(new Character('('));

		//if the first character is '-',this should be deald seprated
		if (s.charAt(0) == '-')
			{
				s = "0" + s;
			}
		
		while (pos < s.length())
		{
			//if the current character is a digit or a letter,the character should be pushed into the stack
			if (Character.isDigit(s.charAt(pos)) || Character.isLetter(s.charAt(pos)) ||
				((pos > 0) && (s.charAt(pos) == '-') && (s.charAt(pos - 1) == '(')))
			{
				if (s.charAt(pos) == '-')
				{
					pos++;				
					tempV.add(new TermNode("-" + read(s.substring(pos,s.length()))));
					s1.push(tempV.clone());
					tempV.clear();
				}
				else 
				{
					tempV.add(new TermNode(read(s.substring(pos,s.length()))));
					s1.push(tempV.clone());
					tempV.clear();
				}
			
			}
			
			//if the current operator has a higher precedence than the element in the top of the stack
			//then the current will be pushed to the stacks
			else if (judgeOperator(((Character)s2.peek()).charValue(),s.charAt(pos)))
			{
					
					s2.push(new Character(s.charAt(pos)));
					
					pos++;
				}

				//else calculate the two element in s1
				else if (((Character)s2.peek()).charValue() != '(')
					{
						
						Vector temp = calculate((Vector)s1.pop(),(Vector)s1.pop(),
											((Character)s2.pop()).charValue());

						if (temp == null)
						{
							pos = 0;
							return null;
						}

						if (!temp.isEmpty() && ((TermNode)temp.get(0)).toString().equals("+E"))
						{

							//because all the method in this class is staic and the varaible is static 
							//the variable after one calculate should be set to the default value,so the next calculate can use it!
							pos = 0;
							return temp;

						}
					
						s1.push(temp.clone());						
						
					}

					//if the top-stack element is '(',pop it!
					else 
					{
						s2.pop();
						pos++;
					}
			
		}
		
		//if s1 contains more than two element do calculate
		while (s1.size() >= 2)
		{
			
			Vector temp = calculate((Vector)s1.pop(),(Vector)s1.pop(),
									((Character)s2.pop()).charValue());
			
			
			if (temp == null)
			{
				pos = 0;
				return null;
			}

			if (!temp.isEmpty() && ((TermNode)temp.get(0)).toString().equals("+E"))
				{

					//because all the method in this class is staic and the varaible is static 
					//the variable after one calculate should be set to the default value,so the next calculate can use it!
					pos = 0;
					return temp;

				}


			s1.push(temp.clone());

		}
		
		//because all the method in this class is staic and the varaible is static 
		//the variable after one calculate should be set to the default value,so the next calculate can use it!
		pos = 0;
		if ((!((Vector)s1.peek()).isEmpty()) && ((TermNode)((Vector)s1.peek()).get(0)).getCoefficient() == 200000001)
		{
			return null;
		}
		//the result shuld be output in specified principle
		sortTerms((Vector)s1.peek());

		return (Vector)s1.pop();
			
	}

	/**method sortTerms
	  *first sort the terms by variableName
	  *then sort the terms by the BS-Exponent sort;
	  */
	private static void sortTerms(Vector terms)
	{
		sortVariableName(terms);
		
		sortExponent(terms);

	}

	/**method sortVariableName
	  *sort the terms by the first variableName
	  */
	private static void sortVariableName(Vector terms)
	{
		for (int i = terms.size() - 1;i > 0 ;i-- )
		{
			for (int j = 0;j < i ;j++ )
			{
				if (((TermNode)terms.get(j)).variableName.isEmpty())
				{
					change(terms,j);
					
				}
				else 
				{
					int min = getMin(terms,j);
					for (int k = 0;k < min;k++ )
					{
						if (((Character)(((TermNode)terms.get(j)).variableName.get(k))).charValue() > 
						((Character)(((TermNode)terms.get(j + 1)).variableName.get(k))).charValue())
						{
							change(terms,j);
							break;
						}
						else if (((Character)(((TermNode)terms.get(j)).variableName.get(k))).charValue() < 
						((Character)(((TermNode)terms.get(j + 1)).variableName.get(k))).charValue())
						{
							break;
						}
					}
				}
				
			}
		}
	}

	/**method sortExponent
	  *sort the terms by BS-Exponent sort
	  */
	private static void sortExponent(Vector terms)
	{
		for (int i = terms.size() - 1;i > 0 ;i-- )
		{
			for (int j = 0;j < i ;j++ )
			{			
				int min = getMin(terms,j);
				for (int k = 0;k < min ;k++ )
				{
			
					if (((Character)(((TermNode)terms.get(j)).variableName.get(k))).charValue() == 
						((Character)(((TermNode)terms.get(j + 1)).variableName.get(k))).charValue())
					{
					
						if (((Integer)(((TermNode)terms.get(j)).exponent.get(k))).intValue() < 
							((Integer)(((TermNode)terms.get(j + 1)).exponent.get(k))).intValue())
							if (k == 0)
							{
								change(terms,j);
								break;			
							}
							else if ( (((Integer)(((TermNode)terms.get(j)).exponent.get(k - 1))).intValue() == 
											((Integer)(((TermNode)terms.get(j + 1)).exponent.get(k - 1))).intValue()))
							{		
								
								change(terms,j);
								break;										
							}
					}
				}
			}
		}

	}

	/**getMin
	  *get the minimum number of the VariableName of the specified terms
	  */
	private static int getMin(Vector terms,int i)
	{
		int min  = ((TermNode)terms.get(i)).variableName.size();
		if (((TermNode)terms.get(i)).variableName.size() > ((TermNode)terms.get(i + 1)).variableName.size())
		{
			min = ((TermNode)terms.get(i + 1)).variableName.size();
		}

		return min;
	}
		
	/**method change
	  *change the specified terms
	  */
	private static void change(Vector terms,int i)
	{
		TermNode tempTerm = (TermNode)((TermNode)terms.get(i)).clone();
		terms.setElementAt(terms.get(i + 1),i);
		terms.setElementAt(tempTerm,i + 1);
	}

	/**method judgeOperator
	  *judge the operate's relation
	  *if op1 < op2 
	  *return true
	  *else return false
	  */
	private static boolean judgeOperator(char op1,char op2)
	{

		int fg1,fg2;

		fg1 = 0;
		fg2 = 0;
		
		//set the in-stack operator's precedence
		//notice that the precedence in-stack and out-stack of the same operater are different!
		//And ')' will never be pushed into the stack!
		switch (op1)
		{
		case '+':case '-':
			fg1 = 1;
			break;
		case '*':case '/':
			fg1 = 2;
			break;
		case '^':
			fg1 = 3;
			break;
		case '(':
			fg1 = 0;
			break;
		
		}
		
		//set the current operator's precedence
		switch (op2)
		{
		case '+':case '-':
			fg2 = 1;
			break;
		case '*':case '/':
			fg2 = 2;
			break;
		case '^':
			fg2 = 4;
			break;
		case '(':
			fg2 = 4;
			break;
		case ')':
			fg2 = 0;
			break;
		}

		if (fg1 < fg2)
		{
			return true;
		}
		else return false;
	}
	
	/**method read
	  *read the next term
	  */
	private static String read(String s)
	{
		int len = 0;//to store the length of current term

		StringTokenizer token = new StringTokenizer(s,"+-()*^");

		String temp = token.nextToken();

		//modify the pos index
		len +=temp.length();
		pos += len;

		return temp;
	}

	/**method calculate
	  *to calculate the terms
	  */
	private static Vector calculate(Vector v2,Vector v1,char operate)
	{
		Vector tempVector = new Vector();
		
		switch (operate)
		{
		case '+':
			return plus(v1,v2);
		case '-':
			return minuse(v1,v2);
		case '*':
			return times(v1,v2);
		case '^':	
			if (v2.size() > 0)
			{
				return pow(v1,((TermNode)v2.get(0)).getCoefficient());
			}
			else return pow(v1,0);
					
		}

		return (Vector)tempVector.clone();

	}

	/**method plus
	  *plus the two terms
	  */
	private static Vector plus(Vector v1,Vector v2)
	{
		//search v1 and v2 one by one
		for (int i = 0;i < v1.size();i++)
			for (int j = 0;j < v2.size();j++)
			{
				//if one element in v1 has the same variable(contains the nanme and exponent),plus them
				if (equals((TermNode)v1.get(i),(TermNode)v2.get(j)))
				{
					
					((TermNode)v1.get(i)).setCoefficient(((TermNode)v1.get(i)).getCoefficient() + ((TermNode)v2.get(j)).getCoefficient());
					
					if (((TermNode)v1.get(i)).getCoefficient() == 200000001)
					{

						return null;
					}
					//the v2[j] has be add to the corresponding v1 element so remove it
					v2.remove(j);
			
				}
			}

		//the left element in v2 will be added to v1's tail
		if (!v2.isEmpty())
		{
			for (int i = 0;i < v2.size();i++ )
			{
				v1.add(v2.get(i));
			}
		}

		//maby the coefficient after plus will be 0 and this element should be remove
		int i = 0;
		while (i < v1.size())
		{

			if (((TermNode)v1.get(i)).getCoefficient() == 0)
			{
				v1.removeElementAt(i);
				i = 0;
			}
			else i++;
		}
		return v1;
		
	}

	/**method minuse
	  *minuse the two terms
	  */
	private static Vector minuse(Vector v1,Vector v2)
	{
		//this part is the same as the plus
		for (int i = 0;i < v1.size();i++)
			for (int j = 0;j < v2.size();j++)
			{
				if (equals((TermNode)v1.get(i),(TermNode)v2.get(j)))
				{
					
					((TermNode)v1.get(i)).setCoefficient(((TermNode)v1.get(i)).getCoefficient() - ((TermNode)v2.get(j)).getCoefficient());
					
					if (((TermNode)v1.get(i)).getCoefficient() == 200000001)
					{

						return null;
					}

					v2.remove(j);
			
				}
			}
		if (!v2.isEmpty())
		{
			for (int i = 0;i < v2.size();i++ )
			{
				((TermNode)v2.get(i)).setCoefficient(((TermNode)v2.get(i)).getCoefficient() * -1);
				v1.add(v2.get(i));
			}
		}
		
		int i = 0;
		while (i < v1.size())
		{

			if (((TermNode)v1.get(i)).getCoefficient() == 0)
			{
				v1.removeElementAt(i);
				i = 0;
			}
			else i++;
		}
		return v1;
		
	}
	
	/**method times
	  *time v1 by v2
	  */
	private static Vector times(Vector v1,Vector v2)
	{

		Vector tempVec = new Vector();
		
		//time the element in v1 and v2 one by one
		for (int i = 0;i < v1.size() ;i++ )
		{
			for (int j = 0; j < v2.size();j++ )
			{

				TermNode tempTerm1 = (TermNode)((TermNode)(v1.get(i))).clone();
				TermNode tempTerm2 = (TermNode)((TermNode)(v2.get(j))).clone();
				
				String str = "";
				
				tempTerm1.setCoefficient(tempTerm1.getCoefficient() * tempTerm2.getCoefficient());
				
				if (tempTerm1.getCoefficient() == 200000001)
				{
					return null;
				}

				for (int k = 0;k < tempTerm2.variableName.size();k++ )
				{
					str += tempTerm2.variableName.get(k) + 
														"^" + tempTerm2.exponent.get(k);
				}
				
				//use TermNode's analyse method to complete the task
				tempTerm1.s = tempTerm1.analyse(tempTerm1.s + str);
				
				//change to the vector type so to complete the plus task
				Vector tV = new Vector();
				tV.add(tempTerm1);

				//the result should be PLUS to the final result
				tempVec = plus(tempVec,tV);
				if (tempVec == null)
				{
					return null;
				}
					
			}
		}

		return tempVec;
		
	}

	/**method pow
	  *it is really done by the times part!
	  */
	private static Vector pow(Vector v1,long exp)
	{
		if ((exp == 0) && (v1.isEmpty() || (((TermNode)v1.get(0)).toString() == "")))
		{
			
			Vector temp = new Vector();
			temp.add(new TermNode("E"));//a sign to express 0^0

			return temp;

		}
		else if (exp == 0)
		{
			
			while (!v1.isEmpty())
			{
				v1.remove(v1.size() - 1);
			}
			v1.add(new TermNode("1"));

			return v1;
		}

		Vector temp = (Vector)v1.clone();

		for (int i = 1;i < exp ;i++ )
		{

			v1 = times(v1,temp);
			if (v1 == null)
			{
				return null;
			}
		}

		return v1;
		
	}

	/**method equals
	  *to judge if the two terms have the same variable and exponent
	  */
	private static boolean equals(TermNode term1,TermNode term2)
	{
		
		if (term1.variableName.equals(term2.variableName) && term1.exponent.equals(term2.exponent))
		{
		
			return true;
		}

		return false;
	}


};