저번시간에 만들었던 Deque를 사용하여 버킷정렬을 연습해보기로 했다.



우선 버킷정렬이 무엇인지 알아보자.



버킷정렬(Bucket Sort) 이란??


n개의 데이터를 정렬할 때 같은 크기의 간격을 갖는 n개의 버켓에 데이터를 분배한다. 입력 데이터가 균일하게 분포되었다면 각 버켓에는 1개의 데이터가 있게 되지만, 균일하게 분포되지 않으면 다수의 데이터가 버켓에 들어 갈 수 있으며 각 버켓의 데이터는 정렬하여 저장한다. n개의 모든 데이터를 버켓에 분배하였다면 버켓 번호 순으로 스캔하여 출력하면 정렬된 데이터를 얻게 된다.


[예제] 최대 2자리를 갖는 정수 (0부터 99까지의 정수) 10개를 버켓 정렬한다고 하자. 각 버켓은 같은 크기의 간격 (0-9, 10-19, 20-29,, 90-99)을 갖는 10개의 버켓을 만들어 데이터를 해당 버켓에 분배한다. 각 버켓에 분배된 데이터는 정렬한다. 다음 버켓 번호 순으로 데이터를 모으면 정렬된 데이터가 된다. 다음은 배열에 10개의 정수 [22, 43, 27, 31, 83, 7, 92, 69, 36, 25]를 버켓 정렬한 것을 도식으로 표현하였다. 





그럼 이 버킷정렬을 deque를 통해 어떤 방식으로 이루어질지 알아보자.


우선 정렬이 되지 않은 데이터를 담고 있는 Deque를 만든다. 그리고 그 데이터의 개수만큼의 Deque 배열을 만든다. 그리고 정렬되지 않은 데이터를 담고 있는 Deque에서 하나씩 데이터를 꺼낸다. 그리고 그 데이터에서 배열 인덱스를 구하고 그 인덱스 위치에 있는 Deque에 데이터를 삽입한다.


이때 데이터를 삽입할 때 Deque에 정렬해서 데이터를 삽입해야 나중에 데이터를 정렬되어서 가져올 수 있다. 인덱스에 위치한 Deque가 데이터가 없는경우 addFirstItem메서드를 통해서 데이터를 집어넣는다. 만약 데이터가 있다면 기존에 데이터의 front에 있는 데이터와 비교하여 순서에 맞게 삽입한다. 이때 순서를 찾기위해서 임시 Deque를 사용하는데 이부분은 단순하여 코드를 보면 쉽게 이해할 수 있다.


이렇게 정렬되지 않은 Deque의 데이터를 버킷에 다 집어 넣고 나서 버킷을 순회하면서 정렬된 데이터를 기존 Deque에 삽입한다.


그럼 정렬이 끝난다.


완성된 코드와 실행화면은 아래와 같다.


Deque에서 사용할 인터페이스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package practice3;
 
public interface Deque<T> {
    public void addFirst(T item);
 
    public void addLast(T item);
 
    public T removeFirst();
 
    public T removeLast();
 
    public T peekFirst();
 
    public T peekLast();
 
    public boolean isEmpty();
 
    public int size();
 
    public String toString();
 
}
 
cs


기존에 만든 Deque

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
package practice3;
 
import java.util.ArrayList;
import java.util.List;
 
public class LinkedDeque<T> implements Deque<T>{
    private static class Node<T> {
        private T item;
        private Node<T> next;
        private Node<T> prev;
 
        private Node() {
            next = null;
            prev = null;
        }
 
        private Node(T item) {
            this.item = item;
            next = null;
            prev = null;
        }
    }
 
    private Node<T> front;
    private Node<T> rear;
    private int size;
 
    public LinkedDeque() {
        front = null;
        rear = null;
        size = 0;
    }
 
    @Override
    public void addLast(T item) {
        Node<T> node = new Node<>(item);
        
        if (front == null && rear == null) {
            addFirstItem(node);
        } else {
            rear.next = node;
            node.prev = rear;
            rear = node;
            size++;
        }
    }
 
    @Override
    public void addFirst(T item) {
        Node<T> node = new Node<>(item);
        
        if (front == null && rear == null) {
            addFirstItem(node);
        } else {
            front.prev = node;
            node.next = front;
            front = node;
            size++;
        }
    }
    
    private void addFirstItem(Node<T> item) {
        front = item;
        rear = item;
        size = 1;
    }
 
    @Override
    public boolean isEmpty() {
        return size == 0;
    }
 
    @Override
    public T removeFirst() {
        T item = null;
        if (size == 0) {
            throw new java.util.NoSuchElementException("peek(): deque empty");
        } else if (size == 1) {
            item = front.item;
            front = null;
            rear = null;
            size = 0;
        } else {
            item = front.item;
            front = front.next;
            front.prev = null;
            size--;
        }
        
        return item;
    }
 
    @Override
    public T removeLast() {
        T item = null;
 
        if (size == 0) {
            throw new java.util.NoSuchElementException("peek(): deque empty");
        } else if (size == 1) {
            item = rear.item;
            front = null;
            rear = null;
            size = 0;
        } else {
            item = rear.item;
            rear = rear.prev;
            rear.next = null;
            size--;
        }
        
        return item;
    }
 
    @Override
    public T peekFirst() {
        if (size == 0)
            throw new java.util.NoSuchElementException("peek(): deque empty");
        return front.item;
    }
 
    @Override
    public T peekLast() {
        if (size == 0)
            throw new java.util.NoSuchElementException("peek(): deque empty");
        return rear.item;
    }
 
    @Override
    public int size() { return size; }
 
    @Override
    public String toString() {
        if (0 == size) {
            return "";
        } else {
            List<String> result = new ArrayList<>();
            Node<T> current;
            current = front;
            if (1 == size) {
                return current.item.toString();
            } else {
                while (current != null) {
                    result.add(current.item.toString());
                    current = current.next;
                }
                
                return String.join(",", result);
            }
            
        }
    }
 
    public String reverse() { // 역순으로 출력
        if (0 == size) {
            return "";
        } else {
            List<String> result = new ArrayList<>();
            Node<T> current;
            current = rear;
            if (1 == size) {
                return current.item.toString();
            } else {
                while (current != null) {
                    result.add(current.item.toString());
                    current = current.prev;
                }
                
                return String.join(",", result);
            }
            
        }
    }
 
}
 
cs




Deque를 정렬하는 Bucket Sort 클래스 (이번 문제의 핵심 클래스)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package practice3;
 
public class BucketSort {
    
    public BucketSort() {}
 
    // 들어온 Deque에 데이터를 버킷정렬을 이용하여 정렬 
    public void bucketSort(LinkedDeque<Integer> data) {
        int bucketIdx;
        int value;
        int size = data.size();
        LinkedDeque<Integer>[] bucketArray = new LinkedDeque[data.size()];
        
        // 들어온 덱에 있는 데이터를 버켓으로 정렬 
        while (!data.isEmpty()) {
            value = data.removeFirst();
            
            bucketIdx = (int) (size * (value / Math.pow(10, getNumCnt(value))));
            if (bucketArray[bucketIdx] == null || bucketArray[bucketIdx].isEmpty()) {
                bucketArray[bucketIdx] = new LinkedDeque<Integer>();
                bucketArray[bucketIdx].addFirst(value);
            } else {
                LinkedDeque<Integer> temp = new LinkedDeque<>();
                while (bucketArray[bucketIdx] != null && !bucketArray[bucketIdx].isEmpty() && bucketArray[bucketIdx].peekFirst() < value) {
                    temp.addFirst(bucketArray[bucketIdx].removeFirst());
                }
                bucketArray[bucketIdx].addFirst(value);
                
                while(!temp.isEmpty()) {
                    bucketArray[bucketIdx].addFirst(temp.removeFirst());
                }
            }
        }
        
        // 버켓에 정렬된 데이터를 다시 덱으로 옮기는 작업 
        for (int i = 0; i < size; i++) {
            while (bucketArray[i] != null && !bucketArray[i].isEmpty()) {
                data.addLast(bucketArray[i].removeFirst());
            }
        }
    }
    
    /**
     * 자리수를 구하는 메소드 
     * 
     * @param value
     * @return
     */
    private int getNumCnt(int value) {
        return (int) Math.log10(value) + 1 ;
    }
}
 
cs




각 Deque의 기능을 호출하는 메인 클래스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package practice3;
 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        System.out.println("Enter a command: af(addFirst), al(addLast),\n"
                + "rf(removeFirst), rl(removeLast), pf(peekFirst), pl(peekLast),\n" + "p(rint), r(verse), or q(uit)");
        System.out.print("> ");
 
        Scanner input = new Scanner(System.in);
        String command = input.next();
        LinkedDeque<Integer> deque = new LinkedDeque<Integer>();
        BucketSort bSort = new BucketSort();
        int item;
 
        while (!command.equals("q")) {
            if (command.equals("af")) {
                item = input.nextInt();
                deque.addFirst(item);
            } else if (command.equals("al")) {
                item = input.nextInt();
                deque.addLast(item);
            } else if (command.equals("rf"))
                deque.removeFirst();
            else if (command.equals("rl"))
                deque.removeLast();
            else if (command.equals("s"))
                System.out.println("size: " + deque.size());
            else if (command.equals("pf"))
                System.out.println("Front of the deque: " + deque.peekFirst());
            else if (command.equals("pl"))
                System.out.println("Rear of the deque: " + deque.peekLast());
            else if (command.equals("r"))
                System.out.println(deque.reverse());
            else if (command.equals("p"))
                System.out.println(deque);
            else if (command.equals("bsort"))
                bSort.bucketSort(deque);
            System.out.print("> ");
            command = input.next();
        }
        System.out.println("Commands Terminated.");
        input.close();
    }
}
 
cs





실행결과

Enter a command: af(addFirst), al(addLast),

rf(removeFirst), rl(removeLast), pf(peekFirst), pl(peekLast),

p(rint), r(verse), or q(uit)

> af 45

af 18

af 35

af 43

af 47

af 39

af 64

af 11

af 15

af 90> > > > > > > > > 

> p

90,15,11,64,39,47,43,35,18,45

> bsort

> p

11,15,18,35,39,43,45,47,64,90

> 

큐는 삽입과 삭제가 리스트의 한쪽 방향에서만 이루어지지만 deque는 리스트의 양쪽 끝 모두에서 이루어질 수 있다.


따라서 양쪽 방향 모두 삽입과 삭제가 이루어질 수 있으므로 기존의 큐나 스택으로 사용할 수 있어 유연하게 사용할 수 있다.


사진출처 : https://dh00023.github.io/algorithm/ds/2018/04/25/algorithm-10/





이런 Deque를 직접 구현해 보자.





우선 Deque의 기능을 정리한 인터페이스이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package practice3;
 
public interface Deque<T> {
    public void addFirst(T item);
 
    public void addLast(T item);
 
    public T removeFirst();
 
    public T removeLast();
 
    public T peekFirst();
 
    public T peekLast();
 
    public boolean isEmpty();
 
    public int size();
 
    public String toString();
 
}
 
cs





그리고 인터페이스를 가지고 구현된 Deque

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
package practice3;
 
import java.util.ArrayList;
import java.util.List;
 
public class LinkedDeque<T> implements Deque<T>{
    private static class Node<T> {
        private T item;
        private Node<T> next;
        private Node<T> prev;
 
        private Node() {
            next = null;
            prev = null;
        }
 
        private Node(T item) {
            this.item = item;
            next = null;
            prev = null;
        }
    }
 
    private Node<T> front;
    private Node<T> rear;
    private int size;
 
    public LinkedDeque() {
        front = null;
        rear = null;
        size = 0;
    }
 
    @Override
    public void addLast(T item) {
        Node<T> node = new Node<>(item);
        
        if (front == null && rear == null) {
            addFirstItem(node);
        } else {
            rear.next = node;
            node.prev = rear;
            rear = node;
            size++;
        }
    }
 
    @Override
    public void addFirst(T item) {
        Node<T> node = new Node<>(item);
        
        if (front == null && rear == null) {
            addFirstItem(node);
        } else {
            front.prev = node;
            node.next = front;
            front = node;
            size++;
        }
    }
    
    private void addFirstItem(Node<T> item) {
        front = item;
        rear = item;
        size = 1;
    }
 
    @Override
    public boolean isEmpty() {
        return size == 0;
    }
 
    @Override
    public T removeFirst() {
        T item = null;
        if (size == 0) {
            throw new java.util.NoSuchElementException("peek(): deque empty");
        } else if (size == 1) {
            item = front.item;
            front = null;
            rear = null;
            size = 0;
        } else {
            item = front.item;
            front = front.next;
            front.prev = null;
            size--;
        }
        
        return item;
    }
 
    @Override
    public T removeLast() {
        T item = null;
 
        if (size == 0) {
            throw new java.util.NoSuchElementException("peek(): deque empty");
        } else if (size == 1) {
            item = rear.item;
            front = null;
            rear = null;
            size = 0;
        } else {
            item = rear.item;
            rear = rear.prev;
            rear.next = null;
            size--;
        }
        
        return item;
    }
 
    @Override
    public T peekFirst() {
        if (size == 0)
            throw new java.util.NoSuchElementException("peek(): deque empty");
        return front.item;
    }
 
    @Override
    public T peekLast() {
        if (size == 0)
            throw new java.util.NoSuchElementException("peek(): deque empty");
        return rear.item;
    }
 
    @Override
    public int size() { return size; }
 
    @Override
    public String toString() {
        if (0 == size) {
            return "";
        } else {
            List<String> result = new ArrayList<>();
            Node<T> current;
            current = front;
            if (1 == size) {
                return current.item.toString();
            } else {
                while (current != null) {
                    result.add(current.item.toString());
                    current = current.next;
                }
                
                return String.join(",", result);
            }
            
        }
    }
 
    public String reverse() { // 역순으로 출력
        if (0 == size) {
            return "";
        } else {
            List<String> result = new ArrayList<>();
            Node<T> current;
            current = rear;
            if (1 == size) {
                return current.item.toString();
            } else {
                while (current != null) {
                    result.add(current.item.toString());
                    current = current.prev;
                }
                
                return String.join(",", result);
            }
            
        }
    }
 
}
 
cs




그리고 이 deque를 가지고 테스트를 진행할 Main클래스


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package practice3;
 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        System.out.println("Enter a command: af(addFirst), al(addLast),\n"
                + "rf(removeFirst), rl(removeLast), pf(peekFirst), pl(peekLast),\n" + "p(rint), r(verse), or q(uit)");
        System.out.print("> ");
 
        Scanner input = new Scanner(System.in);
        String command = input.next();
        LinkedDeque<Integer> deque = new LinkedDeque<Integer>();
        int item;
 
        while (!command.equals("q")) {
            if (command.equals("af")) {
                item = input.nextInt();
                deque.addFirst(item);
            } else if (command.equals("al")) {
                item = input.nextInt();
                deque.addLast(item);
            } else if (command.equals("rf"))
                deque.removeFirst();
            else if (command.equals("rl"))
                deque.removeLast();
            else if (command.equals("s"))
                System.out.println("size: " + deque.size());
            else if (command.equals("pf"))
                System.out.println("Front of the deque: " + deque.peekFirst());
            else if (command.equals("pl"))
                System.out.println("Rear of the deque: " + deque.peekLast());
            else if (command.equals("r"))
                System.out.println(deque.reverse());
            else if (command.equals("p"))
                System.out.println(deque);
            System.out.print("> ");
            command = input.next();
        }
        System.out.println("Commands Terminated.");
        input.close();
    }
}
 
cs





출력결과


Enter a command: af(addFirst), al(addLast),

rf(removeFirst), rl(removeLast), pf(peekFirst), pl(peekLast),

p(rint), r(verse), or q(uit)

> af 20

> af 30

> af 10

> p

10,30,20

> rf

> p

30,20

> rl

> p

30

> al 33

> al 22

> p

30,33,22

> r

22,33,30

> p

30,33,22

> af 44

> al 88

> p

44,30,33,22,88

> rl

> rf

> p

30,33,22

> rf

> p

33,22

> rl

> p

33

> q

Commands Terminated.




다음 시간에는 이것을 이용해 버켓 정렬을 구현해보자.

개발을 진행하다보면 기본에 대해 잊어갈때가 있다.

잊지 않기위해 오늘 부터 매주 하나씩 자료구조를 이용한 문제를 풀어봐야겠다.

오늘은 Stack 첫번째 시간으로 문장의 완성도를 확인하는 프로그램을 작성하여 보자.

[제약사항]
- {[(에 대한 괄호들이 정상적으로 닫혀있어야 한다.
- 주석 //, /* 안에 포함된 내용은 무시한다.
- "" double quote에 들어있는 내용을 무시한다.

간단한 프로그램이라 설명은 생략한다.



- Text를 읽고 판별을 진행하는 Main 클래스



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
package practice1;
 
import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.charset.Charset;
import java.nio.file.Paths;
import java.nio.file.StandardOpenOption;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
 
public class Main {
    
    public static void main(String[] args) {
        List<String> fileList = Arrays.asList("practice1_file/paren1.txt""practice1_file/paren2.txt""practice1_file/paren3.txt");
        List<String> readText = new ArrayList<>();
        
        for (String file : fileList) {
            readText(file, readText);
            System.out.println(file + " : " + checkSentence(readText));
            readText.clear();
        }
        
    }
    
    /**
     * @param readText
     * @return
     */
    public static boolean checkSentence(List<String> readText) {
        Stack<BracketType> brackets = new Stack<>();
        boolean isMultiComment = false;
        boolean isDoubleQuote = false;
        
        for (String str : readText) {
            int oneLineCommentIndex = str.indexOf("//");
            
            // line 주석 체크
            if (oneLineCommentIndex > 0) {
                str = str.substring(0, oneLineCommentIndex);
            } else if (oneLineCommentIndex == 0) {
                continue;
            }
            
            for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                
                // 멀티 라인 주석일 경우
                if (isMultiComment) {
                    if ( c == '*' && i + 1 < str.length() && str.charAt(i + 1== '/' ) {
                        isMultiComment = false;
                        i += 1;
                    } else {
                        continue;
                    }
                }
                
                // " 시작인 경우
                if (isDoubleQuote) {
                    if ( c == '"' ) {
                        isDoubleQuote = false;
                        continue;
                    } else {
                        continue;
                    }
                }
                
                // ", /*
                if (c == '"') {
                    isDoubleQuote = true;
                    continue;
                } else if ( c == '/' && i + 1 < str.length() && str.charAt(i + 1== '*' ) {
                    isMultiComment = true;
                    continue;
                }
                 
                // 괄호 체크
                BracketType type = BracketType.getType(c);
                
                if (type != null) {
                    if (!brackets.isEmpty() && brackets.peek().checkBracket(type)) {
                        brackets.pop();
                    } else {
                        brackets.push(type);
                    }
                }
            }
        }
        
        return brackets.isEmpty();
    }
    
    /**
     * 텍스트 읽기
     * 
     * @param fileName
     * @param list
     * @throws IOException
     */
    public static void readText(String fileName, List<String> list) {
        try (FileChannel fileChannel = FileChannel.open(Paths.get(fileName), StandardOpenOption.READ)) {
            ByteBuffer buffer = ByteBuffer.allocate(1024);
            
            Charset charset = Charset.defaultCharset();
            int byteCount;
            
            while (true) {
                byteCount = fileChannel.read(buffer);
                
                if (byteCount == -1)
                    break;
                
                buffer.flip();
                String line = charset.decode(buffer).toString().trim();
                
                if (null == line || line.length() == 0) {
                    continue;
                }
                
                list.add(line);
                buffer.clear();
            }
            fileChannel.close();
        } catch (Exception ex) {
            System.out.println(ex.getMessage());
        }
    }
    
}
cs





- 괄호에 대한 종류를 담고 있는 Enum 클래스
- 각 괄호를 나타내는 Enum 객체마다 괄호가 정상적으로 닫히는지 여부를 체크하는 메소드가 재정의 되어있음



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package practice1;
 
/**
 * 문장의 괄호 종류와 체크로직
 * 
 * @author wedul
 *
 */
public enum BracketType implements CheckBracketI {
    BIG_RIGHT_BRACKET('}') {
        @Override
        public boolean checkBracket(BracketType type) {
            return false;
        }
    },
    SMALL_RIGHT_BRACKET(')') {
        @Override
        public boolean checkBracket(BracketType type) {
            return false;
        }
    },
    SMALL_LEFT_BRACKET('(') {
        @Override
        public boolean checkBracket(BracketType type) {
            return type.equals(SMALL_RIGHT_BRACKET);
        }
    },
    BIG_LEFT_BRACKET('{') {
        @Override
        public boolean checkBracket(BracketType type) {
            return type.equals(BIG_RIGHT_BRACKET);
        }
    },
    MIDDLE_LEFT_BRACKET('[') {
        @Override
        public boolean checkBracket(BracketType type) {
            return type.equals(MIDDLE_RIGHT_BRACKET);
        }
    },
    MIDDLE_RIGHT_BRACKET(']') {
        @Override
        public boolean checkBracket(BracketType type) {
            return false;
        }
    };;
    ;
    
    private char data;
    
    private BracketType(char data) {
        this.data = data;
    }
    
    public char getData() {
        return this.data;
    }
    
    /**
     * getType
     * 
     * @param input
     * @return
     */
    public static BracketType getType(char input) {
        for (BracketType type : values()) {
            if (type.getData() == input) {
                return type;
            }
        }
        
        return null;
    }
}
cs




- enum에서 사용된 인터페이스


1
2
3
4
5
6
7
8
9
10
11
12
13
package practice1;
 
/**
 * 괄호의 종류별로 체크하는 메소드를 포함한 인터페이스
 * 
 * @author wedul
 *
 */
public interface CheckBracketI {
    
    boolean checkBracket(BracketType type);
 
}
cs



결과




테스트 파일


paren1.txt

paren2.txt

paren3.txt



1 3 + 4 * 와 같이 후위 표기되어있는 식을 계산하는 프로그램을 stack을 이용해서 만들어라

주의사항
- 피연산자가 너무 많으면 오류를 발생시켜라.
- 피연산자가 적어도 오류를 발생시켜라
- 연산자가 사칙연산 이외의 것이 나오면 예외를 발생시켜라
- 결과는 소수점 둘째까지 반올림해서 표현하라.
- 예외는 이 프로그램을 위한 예외를 새로 만들어라

구성
- 파일을 읽는 메서드가 담긴 util 클래스
- 동작이 진행되는 Main 클래스
- 이 프로그램의 예외 OperatorException 클래스



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
package practice2;
 
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.charset.Charset;
import java.nio.file.Paths;
import java.nio.file.StandardOpenOption;
import java.util.Arrays;
import java.util.List;
 
/**
 * 유틸 클래
 * 
 * @author jeongcheol
 *
 */
public class UtilClass {
    
    /**
     * 텍스트 파일을 읽어서 List에 삽입 
     * 
     * @param fileName
     * @param list
     */
    public static void readText(String fileName, List<String> list) {
        try (FileChannel fileChannel = FileChannel.open(Paths.get(fileName), StandardOpenOption.READ)) {
            ByteBuffer buffer = ByteBuffer.allocate(1024);
            
            Charset charset = Charset.defaultCharset();
            int byteCount;
            
            while (true) {
                byteCount = fileChannel.read(buffer);
                
                if (byteCount == -1)
                    break;
                
                buffer.flip();
                String line = charset.decode(buffer).toString().trim();
                
                if (null == line || line.length() == 0) {
                    continue;
                }
                
                list.addAll(Arrays.asList(line.split("\n")));
                buffer.clear();
            }
            fileChannel.close();
        } catch (Exception ex) {
            System.out.println(ex.getMessage());
        }
    }
 
}
 
 
package practice2;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
 
import org.apache.commons.lang3.StringUtils;
 
public class Main {
 
    private static final List<String> fileList = Arrays.asList("file/practice1/postfix.txt"  , "file/practice1/postfix1.txt");
    private static final List<String> operator = Arrays.asList("+""-""/""*");
    private static final List<String> readText = new ArrayList<>();
    private static final Stack<String> operand = new Stack<>();
 
    public static void main(String args[]) {
        for (String file : fileList) {
            UtilClass.readText(file, readText);
            readText.stream().forEach(x -> {
                try {
                    process(x);
                } catch (OperatorException e) {
                    System.out.println(e.getMessage());
                }
            });
            readText.clear();
        }
    }
 
    /**
     * 서식 처리 
     * 
     * @param str
     * @throws OperatorException
     */
    private static void process(String str) throws OperatorException {
        // 초기
        operand.clear();
 
        // 빈 문자열 체크
        if (StringUtils.isBlank(str)) {
            return;
        }
 
        for (String ch : str.replaceAll("\\r\\n|\\r|\\n|\\n\\r""").split(" ")) {
            if (StringUtils.isNumeric(ch)) {
                operand.push(ch);
            } else if (operator.contains(ch)) {
                checkOperand();
                
                double operand2 = Double.valueOf(operand.pop());
                double operand1 = Double.valueOf(operand.pop());
                
                switch (ch) {
                case "+":
                    operand.push(String.valueOf(operand1 + operand2));
                    break;
 
                case "-":
                    operand.push(String.valueOf(operand1 - operand2));
                    break;
 
                case "*":
                    operand.push(String.valueOf(operand1 * operand2));
                    break;
 
                case "/":
                    operand.push(String.valueOf(operand1 / operand2));
                    break;
                    
                default:
                    throw new OperatorException("An unsupported operator.\n");
                }
            } else {
                throw new OperatorException(ch + " operator is unsupported operator.\n");
            }
        } 
        
        // 결과 확인
        checkResult();
        
        System.out.printf(" = %.2f\n" ,Double.valueOf(operand.peek()));
        System.out.println();
    }
    
    /**
     * 계산 전 피연산자 개수 체크 
     * 
     * @throws OperatorException
     */
    private static void checkOperand() throws OperatorException {
        if (operand.isEmpty() || operand.size() < 2) {
            throw new OperatorException("Not enough operand.\n");
        }
    }
    
    /**
     * 계산 후 피연산자 개수 체크 
     * 
     * @throws OperatorException
     */
    private static void checkResult() throws OperatorException {
        if (operand.size() != 1) {
            throw new OperatorException("Too many operand.\n");
        }
    }
    
 
}
 
 
package practice2;
 
/**
 * 연산 입센션 추가 
 * 
 * @author jeongcheol
 *
 */
public class OperatorException extends Exception {
 
    private static final long serialVersionUID = 1L;
    
    public OperatorException(String errMsg) {
        super(errMsg);
    }
 
}
cs



결과




postfix.txt

postfix1.txt




+ Recent posts