[Java] Polynomial Calculator 2/2

자료구조 / 2002년 2학기 / 문병로 교수님

[PolyManage.java]
/* 다항식의 각 항들을 LinkedList에 넣어 저장하면서, 동시에 그 다항식들의 집합도 LinkedList에 저장하는 방식입니다.
  즉, bigList의 Node 각각은 하나의 다항식(Pn(x))를 뜻하고, smallList의 Node 각각은 다항식에서 하나의 항(3x^2)을 가리킵니다.
  그렇지만, 두 List는 같은 LinkedList 자료구조기 때문에 하나의 LinkedList class를 사용해 구현해서 혼돈이 있을수도 있습니다.(code의 효울성을 위해 반복해서 만들필요는 없다고 생각했습니다.)
  구체적으로 말하자면, bigList의 각 node의 number는 다항식번호(n)이고, data는 작은 LinkedList 하나를 가리키는 레퍼런스라 할 수 있습니다.
  반면, smallList의 number는 각 항의 지수이고, data는 각 항의 계수를 표현하도록 했습니다.(Double형 Object)
  number와 data의 변수형에 관한 것은 LinkedList class를 참조하십시오.
  극단적인 input(예를들어, 다항식이 '0' 이거나, 혹은 'x', '-x', 'x^1000' 와 같은 경우)을 고려해서 짜도록 노력했습니다. */

import java.util.*;

public class PolyManage
{
       private LinkedList bigList;  // 하나의 큰 LinkedList를 가짐.

       public PolyManage()
       {
               bigList = new LinkedList();  // 초기화
       }

       public boolean isExist(int polyNumber)
       {
               return bigList.jumpToNodeByNumber(polyNumber);  // 찾는 다항식 번호가 있는지 검사함.
       }

       public boolean enterPoly(int polyNumber, String polyString)  // 새 다항식을 넣는 메쏘드
       {
               LinkedList newSmallList = new LinkedList();  // 작은 List를 하나 만듬(다항식이 들어갈 리스트).
               
               polyString = removeWhiteSpace(polyString);  // 입력받은 String의 모든 공백을 일단 없앰(메쏘드 정의는 아래쪽에).

               if (!doubleSignCheck(polyString))  // 혹시 부호(+,-)가 중복되어 있는지 검사함.
                       return false;  // 중복되어 있다면 새 다항식 입력 실패라고 return.

               polyString = standardizePoly(polyString + '+');  // 스트링을 표준화(아래쪽에 정의)하고, 처리를 효율적으로 하기 위해 맨끝에 '+'를 하나 넣어줌.

               double coeff = 0;
               int exp = 0;                // 계수와 지수를 초기화
               int index = polyString.indexOf("x^");  // index는 최초로 x^ 문자열이 나오는 부분의 인덱스.
               int indexBuffer;        // 다음 iteration을 위해 임시로 저장하는 인덱스 버퍼.
               try
               {
                       while (index != -1)                // 더이상 x^가 발견되지 않을 때 까지.
                       {
                               if (index==0 || (index==1 && polyString.charAt(0)=='+')) // 스트링이 "x^...."로 시작하거나 "+x^..."로 시작하면 계수 = 1.
                                       coeff = 1;
                               else if (index == 1 && polyString.charAt(0)=='-')  // 스트링이 "-x^..."로 시작하면 계수 = -1
                                       coeff = -1;
                               else
                                       coeff = Double.parseDouble(polyString.substring(0,index));  // 그 외의 경우에는 x^ 앞쪽 substring을 double형으로 변환한 것이 계수.
                                                                                                                                                               // 만약 double형으로 변환하는데 exception이 발생하면 아래쪽에서 catch.                                
                               indexBuffer = index;  // 현재 index를 버퍼에 저장해둠.
                               while (polyString.charAt(index)!='+' && polyString.charAt(index)!='-') index++;  // x^ 뒤에 최초로 부호가 나오는 곳까지 index를 이동.
                               exp = Integer.parseInt(polyString.substring(indexBuffer+2,index));  // x^ 와 부호 사이의 substring을 int로 변환한 것이 지수. 마찬가지로 exception은 catch
                               newSmallList.sortedInsertByNumber(exp, new Double(coeff));  // 작은 list에 첫번째 항을 추가. 지수를 기준으로 정렬이 되도록 삽입함(LinkedList class 참조).
                               polyString = polyString.substring(index);  // 더해진 항 부분은 떼어버림. 즉, 지수 뒷부분부터가 새로운 string이 됨.
                               index = polyString.indexOf("x^");  // 다음 x^가 나오는 index를 찾음.
                       }
               }

               catch (NumberFormatException e)  // 혹시 double이나 int형으로 변환하는데 중간에 문자가 들어가 있거나 하면 exception 발생
               {
                       return false;  // 입력이 실패했다고 return
               }

               removeZeroCoeffTerm(newSmallList);  // 리스트에서 data가 0인 node. 즉, 계수가 0인 항은 필요 없으므로 삭제함(아래쪽에 정의).
               bigList.addANodeToEnd(polyNumber, newSmallList);  // 큰 리스트에 다항식번호를 매겨서 새 다항식을 추가함.
               return true;  // 입력이 성공했다고 return
       }

       private String removeWhiteSpace(String s)  // 스트링의 공백을 없애는 메쏘드.
       {
               StringTokenizer st = new StringTokenizer(s);  // 공백을 기준으로 나뉘는 Tokenizer
               String newString = new String();
               while (st.hasMoreTokens()) newString += st.nextToken();  // 나뉘어진 것들을 다시 더함. 자연스레 공백은 사라짐.
               return newString;
       }

       private String standardizePoly(String s)  // 다항식을 표준화하는 작업.
       {
               boolean caught = true;  // 이 전에 부호(+,-)가 catch 되었는가를 기억하고 있는 변수. 맨 앞에 아무것도 없으면 +가 있었다고 볼 수 있으므로 초기값은 true.
               char curChar;        // String의 현재 문자.

               if (s.charAt(0) == 'x')  // 만약 첫문자가 'x'라면
                       s = "1" + s;                // 앞에 계수 역할을 하는 1을 더해줌("+x..."로 시작하거나 "-x..."로 시작하는것은 enterPoly()에서 처리.

               for (int i=1; i<s.length(); i++)  // 첫번째에 x,+,- 가 나오는 경우는 이미 처리했다고 보고, 두번째 문자부터 검사함.
               {                        
                       curChar = s.charAt(i);
                       if (curChar=='+' || curChar=='-')        // 현재 문자가 부호일 때.
                       {
                               if (caught)  // 이전에 부호가 catch가 되고, 이번에 부호가 catch될때까지 'x'가 한번도 안나왔다면
                               {
                                       s = s.substring(0,i) + "x^0" + s.substring(i);        // 상수항이라고 볼 수 있으므로 뒤에 x^0을 추가.
                                       caught = false;  // 현재 'x'가 발견되었다고 볼 수 있으므로 false로 설정.
                               }
                               else
                                       caught = true;  // 만약 이전 부호와 지금 부호 사이에 'x'가 있었다면 값을 다시 true로 설정.
                       }
                       else if (curChar=='x')  // 현재 문자가 'x'일 때.
                       {
                               caught = false;  // 이 부분은 상수항이 아니므로 false라고 설정해주고
                               if (s.charAt(i+1)=='+' || s.charAt(i+1)=='-')  // 혹시 바로 뒤에 부호가 있으면 x^1 항이므로, 뒤에 ^1을 추가.
                                       s = s.substring(0,i+1) + "^1" + s.substring(i+1);
                       }
               }

               return s;
       }

       private boolean doubleSignCheck(String s)  // 부호가 연달아 나오는 경우를 check
       {
               for (int i=0; i<s.length()-1; i++)
                       if (s.charAt(i)=='+' || s.charAt(i)=='-')
                               if (s.charAt(i+1)=='+' || s.charAt(i+1)=='-')
                                       return false;  // 부호가 연달아 나왔으면 false를 return.
               return true;  // 정상이면 true를 return
       }

       private void removeZeroCoeffTerm(LinkedList l)  // 계수가 0인 항을 지우는 메쏘드.
       {
               l.resetIteration();
               while (l.moreToIterate())
               {
                       if (((Double)l.getDataAtCurrent()).doubleValue() == 0)  // 계수가 0이라면
                               l.deleteCurrentNode();  // 그 항을 지움.
                       else
                               l.goToNext();
               }
       }

       public void erasePoly(int polyNumber)  // 다항식을 지우는 메쏘드.
       {
               bigList.resetIteration();
               if(bigList.jumpToNodeByNumber(polyNumber))  // 다항식 번호를 이용해서 검색, 이동.
                       bigList.deleteCurrentNode();                        // 현재 다항식을 삭제.
               else
                       System.out.println("> No P" + polyNumber + "(x) exists!");  // 검색에 실패했을 경우 메시지 출력.
       }
       
       public void evalPoly(int polyNumber, double evalValue)  // 다항식의 값을 계산하는 메쏘드.
       {
               if (bigList.jumpToNodeByNumber(polyNumber))                // 다항식 번호를 이용해서 검색, 이동.
               {
                       double evalResult = 0;  // 계산한 값을 저장할 변수.
                       LinkedList list = (LinkedList)bigList.getDataAtCurrent();  // 찾은 다항식을 불러옴.
                       list.resetIteration();
                       while(list.moreToIterate())
                       {
                               evalResult += ((Double)list.getDataAtCurrent()).doubleValue() * Math.pow(evalValue, list.getNumberAtCurrent());
                               list.goToNext();  // (계수 * evalValue^지수) 를 계속 더해감.
                       }
               
                       System.out.println("> P" + polyNumber + "(" + evalValue + ") = " + evalResult);  // 결과 출력.
               }
               else
                       System.out.println("> No P" + polyNumber + "(x) exists!");  // 검색에 실패했을 경우 메시지 출력.
       }

       public void printPoly()  // 다항식들을 출력하는 메쏘드.
       {
               if (bigList.isEmpty())  // 다항식이 하나도 없을 경우.
                       System.out.println("> No P(x)'s Exists!");
               else
               {
                       int polyNumber;
                       LinkedList smallList;
                       bigList.resetIteration();
                       while(bigList.moreToIterate())
                       {
                               polyNumber = bigList.getNumberAtCurrent();  // 다항식 번호를 불러옴.
                               System.out.print("> P" + polyNumber + "(x) =");
                               printEachPoly((LinkedList)bigList.getDataAtCurrent());  // 다항식을 불러와서, 각 다항식을 출력하는 메쏘드로 보냄.
                               bigList.goToNext();
                       }
               }
       }

       private void printEachPoly(LinkedList poly)  // 각 다항식을 출력하는 메쏘드.
       {
               poly.resetIteration();
               boolean first = true;  // 첫번째 항인지를 기억하고 있는 변수.
               double coeff;
               int exp;
               if (poly.isEmpty())  // 항이 하나도 없는 다항식일 경우.
                       System.out.println(" 0");  // 0을 출력.
               else
               {
                       while(poly.moreToIterate())
                       {
                               coeff = ((Double)poly.getDataAtCurrent()).doubleValue();  // 계수 읽음.
                               exp = poly.getNumberAtCurrent();  // 지수 읽음.
                       
                               if (coeff > 0)  // 계수가 양인데,
                               {
                                       if (first)  // 첫번째 항이면
                                               System.out.print(" ");  // 앞에 '+'를 출력하지 않음.
                                       else
                                               System.out.print(" + ");  // 첫번째 항이 아니면 '+' 부호를 출력.
                               }
                               else  // 계수가 음일 경우. (계수가 0인 경우는 미리 다 없앴다고 생각함.)
                               {
                                       if (first)  // 첫번째 항이면
                                               System.out.print(" -");  // - 부호 뒤에 한칸 안띄움.
                                       else
                                               System.out.print(" - "); // - 부호 뒤에 한칸 띄움. ㅡㅡ;;;;; 스펙에 그렇게 되어 있길래...
                                       coeff = Math.abs(coeff);  // 출력하는 계수는 절대값을 취함. (부호는 이미 출력했으므로)
                               }

                               if (coeff!=1 || (coeff==1 && exp==0))  // 계수가 1이 아니거나, 계수가 1이더라도 상수항일 경우에만 계수를 출력.
                               {
                                       if (coeff == (int)coeff)
                                               System.out.print((int)coeff);  // 만약 정수면 뒤에 ".0"을 출력하지 않기 위해
                                       else
                                               System.out.print(coeff);
                               }

                               switch (exp)
                               {
                               case 0 :
                                       break;  // 상수항이면 지수를 출력하지 않음.
                               case 1 :
                                       System.out.print("x");  // 지수가 1 이면 "x"만 출력.
                                       break;
                               default :
                                       System.out.print("x^" + exp);  // 그 외의 경우에는 "x^지수"를 출력.
                               }
                               first = false;  // 이젠 더 이상 첫번째 항이 아님.
                               poly.goToNext();
                       }
                       System.out.println();
               }
       }

       public void addPoly(int pn1, int pn2)  // 두 다항식을 더해서 출력하는 메쏘드.
       {
               if (bigList.jumpToNodeByNumber(pn1))  // 첫번째 다항식을 다항식 번호로 검색, 이동.
               {
                       LinkedList poly1 = (LinkedList)bigList.getDataAtCurrent();  // 첫번째 다항식 읽어옴.
                       if (bigList.jumpToNodeByNumber(pn2))  // 두번째 다항식을 다항식 번호로 검색, 이동.
                       {
                               LinkedList poly2 = (LinkedList)bigList.getDataAtCurrent();  // 두번째 다항식 읽어옴.
                               System.out.print("P" + pn1 + "(x) + P" + pn2 + "(x) =");
                               printEachPoly(calculateAdd(poly1, poly2));   // 두 다항식을 더한것을 출력.
                       }
                       else
                               System.out.println("> No P" + pn2 + "(x) exists!");  // 두번째 다항식을 찾지 못했을 경우.
               }
               else
                       System.out.println("> No P" + pn1 + "(x) exists!");  // 첫번째 다항식을 찾지 못했을 경우.
       }

       private LinkedList calculateAdd(LinkedList a, LinkedList b)  // 두 다항식을 더하는 메쏘드.
       {
               a.resetIteration();
               b.resetIteration();
               LinkedList newList = new LinkedList();  // 새 리스트를 하나 만듬.
               while (a.moreToIterate())
               {
                       newList.sortedInsertByNumber(a.getNumberAtCurrent(), a.getDataAtCurrent());
                       a.goToNext();  // 첫번째 다항식의 모든 항을 새 다항식에 넣음.
               }
               while (b.moreToIterate())
               {
                       newList.sortedInsertByNumber(b.getNumberAtCurrent(), b.getDataAtCurrent());
                       b.goToNext();  // 두번째 다항식의 모든 항을 새 다항식에 넣으면서 정렬함(지수가 같으면 게수를 더함, 즉 더하는 효과와 같음).
               }
               removeZeroCoeffTerm(newList);  // 계수가 0인 항을 없앰.
               return newList;                // 새로 만든 리스트를 return.
       }

       public void mulPoly(int pn1, int pn2) // 두 다항식을 곱해서 출력하는 메쏘드. 자세한 주석은 addPoly() 함수와 유사.
       {
               if (bigList.jumpToNodeByNumber(pn1))
               {
                       LinkedList poly1 = (LinkedList)bigList.getDataAtCurrent();
                       if (bigList.jumpToNodeByNumber(pn2))
                       {
                               LinkedList poly2 = (LinkedList)bigList.getDataAtCurrent();                                
                               System.out.print("P" + pn1 + "(x) * P" + pn2 + "(x) =");
                               printEachPoly(calculateMul(poly1, poly2));
                       }
                       else
                               System.out.println("> No P" + pn2 + "(x) exists!");
               }
               else
                       System.out.println("> No P" + pn1 + "(x) exists!");
       }

       private LinkedList calculateMul(LinkedList a, LinkedList b)  // 두 다항식을 곱하는 메쏘드.
       {
               LinkedList newList = new LinkedList();
               a.resetIteration();
               while (a.moreToIterate())
               {
                       b.resetIteration();
                       while (b.moreToIterate())
                       {
                               newList.sortedInsertByNumber(a.getNumberAtCurrent() + b.getNumberAtCurrent(),
                                       new Double(((Double)a.getDataAtCurrent()).doubleValue() * ((Double)b.getDataAtCurrent()).doubleValue()));
                               b.goToNext();  // (a의 항 하나, b의 항 하나)의 모든 쌍에 대해 지수는 서로 더하고 계수는 서로 곱해서 새로운 리스트에 넣음.
                       }
                       a.goToNext();
               }
               removeZeroCoeffTerm(newList);
               return newList;
       }

       public void divPoly(int pn1, int pn2)  // 두 다항식을 나누는 메쏘드.
       {
               if (bigList.jumpToNodeByNumber(pn1))
               {
                       LinkedList poly1 = (LinkedList)bigList.getDataAtCurrent();
                       if (bigList.jumpToNodeByNumber(pn2))
                       {
                               LinkedList poly2 = (LinkedList)bigList.getDataAtCurrent();
                               poly1.resetIteration();
                               poly2.resetIteration();
                               if (poly2.isEmpty() || (poly1.getNumberAtCurrent()<poly2.getNumberAtCurrent()))
                                       System.out.println("> Undefined!");  // 피제수의 차수가 제수의 차수보다 작은 경우.
                               else
                               {
                                       LinkedList q = new LinkedList();  // 몫은 비어 있는 상태.
                                       LinkedList r = poly1.listCopy();  // 나머지는 피제수의 값을 일단 그대로 copy.
                                       r.resetIteration();  // 각 다항식의 최고차 항만을 생각했을때,
                                       while (!r.isEmpty() && r.getNumberAtCurrent() >= poly2.getNumberAtCurrent()) // 나머지가 0이 되거나, 나머지의 차수가 제수의 차수보다 작아질때 까지.
                                       {
                                               q.addANodeToEnd(r.getNumberAtCurrent() - poly2.getNumberAtCurrent(),
                                                       new Double( ((Double)r.getDataAtCurrent()).doubleValue() / ((Double)poly2.getDataAtCurrent()).doubleValue()) );
                                                       // 지수가 (나머지의 지수 - 제수의 지수) 이고, 계수가 (나머지의 계수 / 제수의 계수) 인, 항을 몫에다가 더함. (즉, 3x^2 나누기 x 라면 (지수:2-1=1, 계수:3/1=3)인 3x 항을 몫에 더하는 꼴이 됨.)
                                               r = calculateAdd(scalarTimesList(-1,calculateMul(q, poly2)), poly1); // 새로운 나머지 r은 ( (-1)*(몫 * 제수) + 피제수 ) 즉, (피제수 - 몫*제수)가 됨.
                                               removeZeroCoeffTerm(r);
                                               removeZeroCoeffTerm(q);  // 몫과 나머지의 필요없는 항을 삭제.
                                               r.resetIteration();
                                               poly2.resetIteration();  // 최고 차수를 검사해야 하므로 다시 iteration을 초기화함.
                                       }

                                       System.out.print("> Q" + pn1 + pn2 + "(x) =");
                                       printEachPoly(q);
                                       System.out.print("> R" + pn1 + pn2 + "(x) =");
                                       printEachPoly(r);                // 계산 결과 출력.
                               }
                       }
                       else
                               System.out.println("> No P" + pn2 + "(x) exists!");
               }
               else
                       System.out.println("> No P" + pn1 + "(x) exists!");
       }

       private LinkedList scalarTimesList(double scalar, LinkedList l) // 모든 계수에 일정한 상수를 곱해주는 메쏘드. 즉, 다항식 전체가 scalar배 됨.
       {
               LinkedList newList = new LinkedList();
               l.resetIteration();
               while (l.moreToIterate())
               {
                       newList.addANodeToEnd(l.getNumberAtCurrent(), new Double(scalar * ((Double)l.getDataAtCurrent()).doubleValue()));
                       l.goToNext();
               }
               return newList;
       }
}