자료구조 과제 #1

요구사항

2012.4.02
    
 자료구조 Homework #1

1. Basic Description
1) List에 대한 command line interpreter를 개발한다.
2) List
- empty이거나 하나 이상의 item으로 구성되며, item은 공백없이 ASCII alphabet으로 이루어진
string이거나, list이다.
- list는 '('로 시작하고 ')'로 마친다
- list 내에 포함된 list는 '()'를 구별자로 사용한다.
3) User interface
- file로 command를 입력받아서 결과를 file로 출력함
- 입력 file과 출력 file의 이름을 program argument로 입력 받음
예) > interpreter input output

2. Commands
1) reverse
사용법) reverse list 
list내의 item들을 역순으로 나열하여 만들어지는 list를 생성하고 이를 출력한다.

예)
> reverse (a b c d)
(d c b a)
> reverse (oneword)
(oneword)
> reverse (one two three)
(three two one)
> reverse (a b (c d (e f)) g (h i))
((h i) g (c d (e f)) b a)
> reverse
no operand

2) append
사용법) append list1 | list2
list1과 list2는 '|'로 구별되며, list1의 item들에 list2의 item들이 덧붙여져서 만들어지는 list를

생성하고, 이를 출력한다.
예)
> append |
no operand
> append
no operand
> append (a)
(a)
> append (b) |
(b)
> append | (aa)
(aa)
> append (one) | (two three four)
(one two three four)
> append (a b (c d)) | ((e f g) (h i) j)
(a b (c d) (e f g) (h i) j)
> append (a b (c d)) | (k)
(a b (c d) k)

3) flatten
사용법) flatten list
list 내에 있는 list들을 모두 해제하여 내부에 괄호가 없는 list를 생성하고, 이를 출력한다.

사용예)
> flatten
> flatten (a b (c d (e (f p r))) g (h i))
(a b c d e f p r g h i)
> flatten (a b (c d (e (f p r))) g (h i)
one unmatched parenthesis
> flatten (a b (c d (e (f p r))) g (h i
two unmatched parentheses

4) 위의 command들을 복합적으로 사용하는 경우
1)에서 3)에 제시된 command들이 operand의 시작 부분에 연속적으로 나타날 수 있다.
이 경우, right to left associativity를 적용하여 결과를 출력한다.

예)
> reverse append (cat) | (mew)
(mew cat)
> append reverse (cat mew) | (dog)
(mew cat dog)
> append (cat) | reverse (mew dog)
(cat dog mew)
> flatten append (cat) | ((mew) (dog))
(cat mew dog)
> append (cat) | reverse ((mew) (dog))
(cat (dog) (mew))
> flatten append (cat) | reverse ((mew) (dog))
(cat dog mew)
> append reverse (cat mew) | ((dog) (pig) (racoon))
(mew cat (dog) (pig) (racoon))
> append reverse (cat mew) | flatten ((dog) (pig) (racoon))
(mew cat dog pig racoon)


3. 제출물
1) 프로그램 설명서 (*.doc, *.txt, *.hwp 중 선택)
   - 프로그램의 구성 기술
   - 선택한 data structure의 타당성 기술
   -  space complexity, time complexity에 대한 분석
   - 기타 필요한 설명
2) source code (사용한 C compiler의 종류와 version 제시)

4. 제출 기한 및 방법

1) 2012년 4월 27일(금) 자정까지 도착하는 제출물만 인정
2) 제출 방법: e-class로 제출 

5. 개발 시 주의 사항
1) 이번 학기를 통해 배운 linked list와 array 중에서 선택하여 구현할 수 있다.
2) command가 복합적으로 사용되는 경우를 지원하기 위해, stack이나 queue 등 적합한 것을 선택하
여 구현하되, 선택한 이유에 대한 설명이 '프로그램 설명서'에 포함되어야 한다.
3) 사용하는 programming언어는 C로 제한한다. Visual Studio나 gcc를 사용할 것을 권장한다.
4) command의 operand로 주어지는 list의 item은 영어 alphabet으로만 구성되는 것으로 한다. 영어 alphabet이 아닌 경우 output file에 오류를 출력해야 함

6. 평가 기준
1) 만점: 100점
2) 설명서나 code를 copy한 것으로 판정되면, 원본과 copy본 모두 fail (0점)
3) 과제에 관련해서 어떠한 부정행위라도 발견되면, fail 처리 (0점)
3) compile 실패하면, fail (0점)
4) 제출 기한을 넘기는 경우, fail (0점) 반드시 제출 기한 내에 제출할 것
5) test 사례 14건에 대해 성공 건수 * 5점
6) 프로그램 설명서의 내용과 구성 (30점)
　　- 형식도 고려하지만, 내용의 충실성에 치중하여 채점할 것임


==========================================================

다음은 과제 1 보고서에 반드시 있어야 할 내용입니다.
이 외에도 본인이 개발한 결과물의 "우수성"을 설명하기 위해 필요한 것들을 추가해도 좋습니다.

문서 format은 hwp, doc 모두 허용합니다.

자료구조 과제 보고서

제출일:
학번:
이름:
 
 
1. 과제의 목적
[주: 과제 설명서에 근거하여 이번 과제에서 어떤 기능을 수행하는 프로그램을 개발했는지 기술함]
 
2. 프로그램 구조
2.1 핵심 data structure 설명
[주: command line을 읽어서 processing하기 위해 command line을 해석하기 위해 사용하는 data structure, 이 외에도 프로그램 수행에 있어 중요하다고 생각되는 data structure를 기술함]
[주: data structure의 구조, 용도, 활용 사례 등]
 
2.2 Structure chart
[주: 프로그램 전체 구조를 structure chart를 사용하여 기술함]

2.3 개발 환경
[주: 사용한 compiler version, 운영체제(MS Windows XP, MS Windows 7, Linux 등)]

3. 프로그램 수행 결과 사례
[주: 본인이 test 용으로 사용한 input에 근거해서 output이 어떻게 나오는지 기술]
 
4. 프로그램 복잡도 분석
4.1 Space complexity
[주: command line의 argument의 개수나 command의 개수에 따른 분석]
 
4.2 Time complexity
[주: command line의 argument의 개수나 command의 개수에 따른 분석]
 
5. 돌아보기
[주; 과제 수행에 있어서 가장 어려웠던 점은 무엇이었는가, 어려운 문제를 어떻게 해결했는가, 과제를 통해서 가장 중요하게 배웠다고 생각하는 것은 무엇인가]

신나는 DS

이 문제에 대한 제 구현입니다. https://github.com/huntrax11/DS-HW-1