반응형
자료구조 / 2002년 2학기 / 문병로 교수님
[설명]
Polynomial Calculator : 다항식 계산 프로그램.
Poly.java : 프로그램이 실제 수행되는 main() 메쏘드가 있는 클래스.
PolyManage.java : 다항식의 입력,삭제,계산,덧셈,곱셈,나눗셈 등을 수행하는 클래스.
LinkedList.java : 다항식을 저장하는 자료구조인 링크드 리스트를 구현한 클래스.
[Usage]
다항식 입력
> enter 5
> 5x^2 + 6 x^3 -5x + 0x^3 -5 +2x^3
다항식 출력
> print
다항식 계산
> eval 5 1.5
다항식 삭제
> erase 5
다항식 덧셈
> add 2 5
다항식 곱셈
> mul 2 5
다항식 나눗셈
> div 2 5
[Poly.java]
import java.util.*;
public class Poly
{
public static void main(String[] args)
{
PolyManage pm = new PolyManage(); // 다항식을 다루는 클래스의 오브젝트를 하나 생성.
System.out.print("> "); // 프롬프트 출력.
String input = SavitchIn.readLine(); // 입력을 받음.
String command; // 명령어를 따로 저장할 변수.
int polyNumber, polyNumber2;
double evalValue;
while (!input.equalsIgnoreCase("quit")) // 끝내라는 명령이 나오기까지
{
StringTokenizer st = new StringTokenizer(input); // 인풋을 Tokenizer에 집어 넣고
if (st.hasMoreTokens())
{
command = st.nextToken(); // 첫번째 Token을 명령어라고 보면,
try
{
if (command.equalsIgnoreCase("enter")) // 명령이 enter 라면
{
polyNumber = Integer.parseInt(st.nextToken()); // 그다음 Token을 int로 변환한것이 다항식번호.
commandEndCheck(st); // 명령어가 여기서 끝났는지 검사.
if (pm.isExist(polyNumber)) // 만약 같은 번호의 다항식이 이미 있다면
System.out.println("> P" + polyNumber + "(x) already exists!");
else
{
System.out.print("> "); // 다시 프롬프트를 출력하고
input = SavitchIn.readLine(); // 입력을 받고
if (!pm.enterPoly(polyNumber, input)) // 다항식을 입력하는 함수로 보냄.
syntaxError(); // 만약 입력에 실패했을 경우 syntax error로 판단.
}
}
else if (command.equalsIgnoreCase("erase")) // 명령이 erase일 경우.
{
polyNumber = Integer.parseInt(st.nextToken());
commandEndCheck(st);
pm.erasePoly(polyNumber);
}
else if (command.equalsIgnoreCase("eval")) // 위의 명령어들과 같은 방식.
{
polyNumber = Integer.parseInt(st.nextToken());
evalValue = Double.parseDouble(st.nextToken());
commandEndCheck(st);
pm.evalPoly(polyNumber, evalValue);
}
else if (command.equalsIgnoreCase("print")) // "
{
commandEndCheck(st);
pm.printPoly();
}
else if (command.equalsIgnoreCase("add")) // "
{
polyNumber = Integer.parseInt(st.nextToken());
polyNumber2 = Integer.parseInt(st.nextToken());
commandEndCheck(st);
pm.addPoly(polyNumber, polyNumber2);
}
else if (command.equalsIgnoreCase("mul")) // "
{
polyNumber = Integer.parseInt(st.nextToken());
polyNumber2 = Integer.parseInt(st.nextToken());
commandEndCheck(st);
pm.mulPoly(polyNumber, polyNumber2);
}
else if (command.equalsIgnoreCase("div")) // "
{
polyNumber = Integer.parseInt(st.nextToken());
polyNumber2 = Integer.parseInt(st.nextToken());
commandEndCheck(st);
pm.divPoly(polyNumber, polyNumber2);
}
else // 위의 모든 명령어가 아닐 경우 syntax error
syntaxError();
}
catch (NumberFormatException e) // 다항식 번호를 int형으로 변환하거나, evalValue를 double형으로 변환할때.
{ // exception이 발생하면, syntax error로 간주.
syntaxError();
}
catch (NoSuchElementException e) // 다음 Token이 요구되는데, Token이 더 이상 없을 경우 syntax error로 간주.
{
syntaxError();
}
}
System.out.print("> "); // 다시 프롬프트를 출력하고
input = SavitchIn.readLine(); // 다음 입력을 받음.
}
}
private static void syntaxError() // syntax error로 판단되었을 경우 메세지 출력.
{
System.out.println("> Syntax Error!");
}
private static void commandEndCheck(StringTokenizer st) // 명령어가 끝났는지 check
{
if (st.hasMoreTokens())
syntaxError(); // 남은 Token이 더 있다면 syntax error로 간주.
}
}
[LinkedList.java]
/* LinkedList는 일단 Savitch JAVA에서 가져왔습니다.
Java An Introduction to Computer Science and Programming Second Edition (Walter Savitch) - p698 StringLinkedListWithIterator Class
그렇지만 필요없다고 생각되는 많은 부분을 뺐고,
ListNode는 int형 number와 Object형 data, 그리고 링크, 세 가지를 갖도록 수정했습니다.
또, head는 맨 처음 Node가 되는게 아니라 맨 처음 Node를 가리키는 새로운 Node가 되도록 수정했고,
Node를 마지막에 삽입하는 메쏘드를 만들었습니다. (addANodeToEnd())
그리고, Node를 삽입할때 number에 따라 정렬되도록(맨앞 Node의 number가 가장 크도록) 삽입하는 메쏘드도 추가해서 만들었습니다. (sortedInsertByNumber())
찾는 number가 있는 Node로 current를 옮겨주는 메쏘드 또한 만들었습니다. (jumpToNodeByNumber())
그 외에도 isEmpty(), listCopy() 등을 새로 만들어서 구현했습니다.
즉, 기본적인 구현만 가져왔고, 구체적인 구현부분은 거의 새로 만들거나, 문제에 맞게 수정해서 사용했습니다. */
public class LinkedList
{
private ListNode head;
private ListNode current;
private ListNode previous;
public LinkedList()
{
head = new ListNode(); // head는 link가 null인 new ListNode.
current = null;
previous = null;
}
public void addANodeToEnd(int newNumber, Object newData) // list의 마지막에 node를 추가하는 메쏘드.
{
ListNode position = head;
while (position.link != null)
position = position.link; // list의 마지막까지 position을 이동.
position.link = new ListNode(newNumber, newData, null); // 마지막부분에 새 node를 추가하고, 그 node를 현재 position node가 가리킴.
}
public void resetIteration()
{
current = head.link; // current는 맨 앞 node를 가리키고, previous는 그 앞에 있는 head node를 가리킴.
previous = head;
}
public boolean isEmpty()
{
return (head.link == null); // 맨 앞 node가 null일(없을) 경우.
}
public void goToNext()
{
if (current != null) // 정상적인 iteration중이라면 current는 반드시 null이 아니여야 한다.
{
previous = current;
current = current.link; // previous와 current를 한칸씩 옮김.
}
else if (head.link != null) // list가 비어있지는 않으나, current가 null일 경우.
{
System.out.println("Interated too many times or uninitialized iteration.");
System.exit(0);
}
else // head.link==null. 즉, list가 비어있는 경우.
{
System.out.println("Iteration with an empty list.");
System.exit(0);
}
}
public boolean moreToIterate() // 더 이상 interate가 가능한지 여부
{
return (current != null);
}
public Object getDataAtCurrent() // current node의 data를 return
{
if (current != null)
return (current.data);
else // current가 null일 경우.
{
System.out.println("Getting data when current is not at any node.");
System.exit(0);
}
return null;
}
public int getNumberAtCurrent() // current node의 number를 return
{
if (current != null)
return (current.number);
else // current가 null일 경우.
{
System.out.println("Getting number when current is not at any node.");
System.exit(0);
}
return -1;
}
public boolean jumpToNodeByNumber(int keyNumber) // number를 이용해 그 위치로 current를 이동시켜줌.
{
ListNode position = head;
while(position.link != null) // 더 이상 link값이 없을때까지(맨 끝 node 바로 앞 node 까지)
{
if (keyNumber == position.link.number) // link의 number가 찾는 number라면
{
previous = position; // previous는 현재 position
current = position.link; // current는 찾는 number가 있던 position.link
return true; // 찾기에 성공했다고 return
}
position = position.link;
}
return false; // 찾기에 실패했다고 return
}
public void sortedInsertByNumber(int newNumber, Object newData) // 새로운 node를 삽입시, number에 따라 정렬이 되도록 삽입하는 메쏘드
{
ListNode position = head;
while ((position.link != null) && (newNumber < position.link.number)) // 삽입할 number보다 크거나 같은 number가 나올때까지 iterate 함.
position = position.link;
if (position.link == null || newNumber > position.link.number) // 만약 마지막까지 왔거나, 혹은 삽입할 number가 position.link의 number보다 크다면
position.link = new ListNode(newNumber, newData, position.link); // 해당하는 위치에 node를 삽입.
else
position.link.data = addData(position.link.data, newData); // 만약 number가 position.link.number와 같다면 그 node에 값을 더해줌.
}
private Double addData(Object x, Object y) // 값을 더하는 메쏘드 (data가 Double형 이라고 가정)
{
return new Double(((Double)x).doubleValue() + ((Double)y).doubleValue()); // 두 값을 더해서 return
}
public void deleteCurrentNode() // current node를 지우는 메쏘드
{
if (current != null)
{
previous.link = current.link; // 앞쪽 link를 끊고 새로 연결하고,
current = current.link; // 뒤쪽 link도 끊고 새로 연결함.
}
else
{
System.out.println("Deleting with uninitialized current or an empty list.");
System.exit(0);
}
}
public LinkedList listCopy() // 리스트의 내용을 그대로 복사한 새로운 리스트를 return
{
ListNode position = head.link;
LinkedList returnList = new LinkedList();
while (position != null)
{
returnList.addANodeToEnd(position.number, position.data); // node를 읽어서 새 list의 뒤에다 계속 삽입.
position = position.link;
}
return returnList;
}
private class ListNode
{
private int number;
private Object data;
private ListNode link;
public ListNode()
{
number = 0;
data = null;
link = null;
}
public ListNode(int newNumber, Object newData, ListNode linkValue)
{
number = newNumber;
data = newData;
link = linkValue;
}
}
}
[설명]
Polynomial Calculator : 다항식 계산 프로그램.
Poly.java : 프로그램이 실제 수행되는 main() 메쏘드가 있는 클래스.
PolyManage.java : 다항식의 입력,삭제,계산,덧셈,곱셈,나눗셈 등을 수행하는 클래스.
LinkedList.java : 다항식을 저장하는 자료구조인 링크드 리스트를 구현한 클래스.
[Usage]
다항식 입력
> enter 5
> 5x^2 + 6 x^3 -5x + 0x^3 -5 +2x^3
다항식 출력
다항식 계산
> eval 5 1.5
다항식 삭제
> erase 5
다항식 덧셈
> add 2 5
다항식 곱셈
> mul 2 5
다항식 나눗셈
> div 2 5
[Poly.java]
import java.util.*;
public class Poly
{
public static void main(String[] args)
{
PolyManage pm = new PolyManage(); // 다항식을 다루는 클래스의 오브젝트를 하나 생성.
System.out.print("> "); // 프롬프트 출력.
String input = SavitchIn.readLine(); // 입력을 받음.
String command; // 명령어를 따로 저장할 변수.
int polyNumber, polyNumber2;
double evalValue;
while (!input.equalsIgnoreCase("quit")) // 끝내라는 명령이 나오기까지
{
StringTokenizer st = new StringTokenizer(input); // 인풋을 Tokenizer에 집어 넣고
if (st.hasMoreTokens())
{
command = st.nextToken(); // 첫번째 Token을 명령어라고 보면,
try
{
if (command.equalsIgnoreCase("enter")) // 명령이 enter 라면
{
polyNumber = Integer.parseInt(st.nextToken()); // 그다음 Token을 int로 변환한것이 다항식번호.
commandEndCheck(st); // 명령어가 여기서 끝났는지 검사.
if (pm.isExist(polyNumber)) // 만약 같은 번호의 다항식이 이미 있다면
System.out.println("> P" + polyNumber + "(x) already exists!");
else
{
System.out.print("> "); // 다시 프롬프트를 출력하고
input = SavitchIn.readLine(); // 입력을 받고
if (!pm.enterPoly(polyNumber, input)) // 다항식을 입력하는 함수로 보냄.
syntaxError(); // 만약 입력에 실패했을 경우 syntax error로 판단.
}
}
else if (command.equalsIgnoreCase("erase")) // 명령이 erase일 경우.
{
polyNumber = Integer.parseInt(st.nextToken());
commandEndCheck(st);
pm.erasePoly(polyNumber);
}
else if (command.equalsIgnoreCase("eval")) // 위의 명령어들과 같은 방식.
{
polyNumber = Integer.parseInt(st.nextToken());
evalValue = Double.parseDouble(st.nextToken());
commandEndCheck(st);
pm.evalPoly(polyNumber, evalValue);
}
else if (command.equalsIgnoreCase("print")) // "
{
commandEndCheck(st);
pm.printPoly();
}
else if (command.equalsIgnoreCase("add")) // "
{
polyNumber = Integer.parseInt(st.nextToken());
polyNumber2 = Integer.parseInt(st.nextToken());
commandEndCheck(st);
pm.addPoly(polyNumber, polyNumber2);
}
else if (command.equalsIgnoreCase("mul")) // "
{
polyNumber = Integer.parseInt(st.nextToken());
polyNumber2 = Integer.parseInt(st.nextToken());
commandEndCheck(st);
pm.mulPoly(polyNumber, polyNumber2);
}
else if (command.equalsIgnoreCase("div")) // "
{
polyNumber = Integer.parseInt(st.nextToken());
polyNumber2 = Integer.parseInt(st.nextToken());
commandEndCheck(st);
pm.divPoly(polyNumber, polyNumber2);
}
else // 위의 모든 명령어가 아닐 경우 syntax error
syntaxError();
}
catch (NumberFormatException e) // 다항식 번호를 int형으로 변환하거나, evalValue를 double형으로 변환할때.
{ // exception이 발생하면, syntax error로 간주.
syntaxError();
}
catch (NoSuchElementException e) // 다음 Token이 요구되는데, Token이 더 이상 없을 경우 syntax error로 간주.
{
syntaxError();
}
}
System.out.print("> "); // 다시 프롬프트를 출력하고
input = SavitchIn.readLine(); // 다음 입력을 받음.
}
}
private static void syntaxError() // syntax error로 판단되었을 경우 메세지 출력.
{
System.out.println("> Syntax Error!");
}
private static void commandEndCheck(StringTokenizer st) // 명령어가 끝났는지 check
{
if (st.hasMoreTokens())
syntaxError(); // 남은 Token이 더 있다면 syntax error로 간주.
}
}
[LinkedList.java]
/* LinkedList는 일단 Savitch JAVA에서 가져왔습니다.
Java An Introduction to Computer Science and Programming Second Edition (Walter Savitch) - p698 StringLinkedListWithIterator Class
그렇지만 필요없다고 생각되는 많은 부분을 뺐고,
ListNode는 int형 number와 Object형 data, 그리고 링크, 세 가지를 갖도록 수정했습니다.
또, head는 맨 처음 Node가 되는게 아니라 맨 처음 Node를 가리키는 새로운 Node가 되도록 수정했고,
Node를 마지막에 삽입하는 메쏘드를 만들었습니다. (addANodeToEnd())
그리고, Node를 삽입할때 number에 따라 정렬되도록(맨앞 Node의 number가 가장 크도록) 삽입하는 메쏘드도 추가해서 만들었습니다. (sortedInsertByNumber())
찾는 number가 있는 Node로 current를 옮겨주는 메쏘드 또한 만들었습니다. (jumpToNodeByNumber())
그 외에도 isEmpty(), listCopy() 등을 새로 만들어서 구현했습니다.
즉, 기본적인 구현만 가져왔고, 구체적인 구현부분은 거의 새로 만들거나, 문제에 맞게 수정해서 사용했습니다. */
public class LinkedList
{
private ListNode head;
private ListNode current;
private ListNode previous;
public LinkedList()
{
head = new ListNode(); // head는 link가 null인 new ListNode.
current = null;
previous = null;
}
public void addANodeToEnd(int newNumber, Object newData) // list의 마지막에 node를 추가하는 메쏘드.
{
ListNode position = head;
while (position.link != null)
position = position.link; // list의 마지막까지 position을 이동.
position.link = new ListNode(newNumber, newData, null); // 마지막부분에 새 node를 추가하고, 그 node를 현재 position node가 가리킴.
}
public void resetIteration()
{
current = head.link; // current는 맨 앞 node를 가리키고, previous는 그 앞에 있는 head node를 가리킴.
previous = head;
}
public boolean isEmpty()
{
return (head.link == null); // 맨 앞 node가 null일(없을) 경우.
}
public void goToNext()
{
if (current != null) // 정상적인 iteration중이라면 current는 반드시 null이 아니여야 한다.
{
previous = current;
current = current.link; // previous와 current를 한칸씩 옮김.
}
else if (head.link != null) // list가 비어있지는 않으나, current가 null일 경우.
{
System.out.println("Interated too many times or uninitialized iteration.");
System.exit(0);
}
else // head.link==null. 즉, list가 비어있는 경우.
{
System.out.println("Iteration with an empty list.");
System.exit(0);
}
}
public boolean moreToIterate() // 더 이상 interate가 가능한지 여부
{
return (current != null);
}
public Object getDataAtCurrent() // current node의 data를 return
{
if (current != null)
return (current.data);
else // current가 null일 경우.
{
System.out.println("Getting data when current is not at any node.");
System.exit(0);
}
return null;
}
public int getNumberAtCurrent() // current node의 number를 return
{
if (current != null)
return (current.number);
else // current가 null일 경우.
{
System.out.println("Getting number when current is not at any node.");
System.exit(0);
}
return -1;
}
public boolean jumpToNodeByNumber(int keyNumber) // number를 이용해 그 위치로 current를 이동시켜줌.
{
ListNode position = head;
while(position.link != null) // 더 이상 link값이 없을때까지(맨 끝 node 바로 앞 node 까지)
{
if (keyNumber == position.link.number) // link의 number가 찾는 number라면
{
previous = position; // previous는 현재 position
current = position.link; // current는 찾는 number가 있던 position.link
return true; // 찾기에 성공했다고 return
}
position = position.link;
}
return false; // 찾기에 실패했다고 return
}
public void sortedInsertByNumber(int newNumber, Object newData) // 새로운 node를 삽입시, number에 따라 정렬이 되도록 삽입하는 메쏘드
{
ListNode position = head;
while ((position.link != null) && (newNumber < position.link.number)) // 삽입할 number보다 크거나 같은 number가 나올때까지 iterate 함.
position = position.link;
if (position.link == null || newNumber > position.link.number) // 만약 마지막까지 왔거나, 혹은 삽입할 number가 position.link의 number보다 크다면
position.link = new ListNode(newNumber, newData, position.link); // 해당하는 위치에 node를 삽입.
else
position.link.data = addData(position.link.data, newData); // 만약 number가 position.link.number와 같다면 그 node에 값을 더해줌.
}
private Double addData(Object x, Object y) // 값을 더하는 메쏘드 (data가 Double형 이라고 가정)
{
return new Double(((Double)x).doubleValue() + ((Double)y).doubleValue()); // 두 값을 더해서 return
}
public void deleteCurrentNode() // current node를 지우는 메쏘드
{
if (current != null)
{
previous.link = current.link; // 앞쪽 link를 끊고 새로 연결하고,
current = current.link; // 뒤쪽 link도 끊고 새로 연결함.
}
else
{
System.out.println("Deleting with uninitialized current or an empty list.");
System.exit(0);
}
}
public LinkedList listCopy() // 리스트의 내용을 그대로 복사한 새로운 리스트를 return
{
ListNode position = head.link;
LinkedList returnList = new LinkedList();
while (position != null)
{
returnList.addANodeToEnd(position.number, position.data); // node를 읽어서 새 list의 뒤에다 계속 삽입.
position = position.link;
}
return returnList;
}
private class ListNode
{
private int number;
private Object data;
private ListNode link;
public ListNode()
{
number = 0;
data = null;
link = null;
}
public ListNode(int newNumber, Object newData, ListNode linkValue)
{
number = newNumber;
data = newData;
link = linkValue;
}
}
}
반응형