Skip to content

Instantly share code, notes, and snippets.

@ksundong

ksundong/자료구조-스터디-3주차.md

Created August 10, 2020 01:47
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ksundong/f0f5fc50b4d6c4218a7a307d90d36c14 to your computer and use it in GitHub Desktop.
Save ksundong/f0f5fc50b4d6c4218a7a307d90d36c14 to your computer and use it in GitHub Desktop.
Download ZIP
자료구조 스터디 3주차
Raw
자료구조-스터디-3주차.md

자바 자료구조 스터디 3주차

이 md 파일은 Typora 에서 작성되었습니다. 읽으실 때, Typora 에서 읽으시는 것이 가장 보기에 좋습니다.

[TOC]

연결 리스트(Linked List) 3

원형 연결 리스트(Circular Linked List)

아무것도 안보고 구현할 수 있나요?

대답이 무엇이던지 간에 저희의 목적인 "자료구조를 언제 어떨 때 써야할 지 아는 것" 에 포커스를 맞춰 공부하는 것이 좋을 것 같습니다.

직접구현을 했던 이유도, 자료구조를 이해하기 위함이죠.

원형 연결 리스트의 이해

마지막 노드가 첫번째 노드를 가리키면 됩니다.

여기서 말하듯이 추가 과정을 tail에 의존하도록 놓는 방법은 생각하지 못했네요.

변형된 원형 연결 리스트의 ADT

SortedList가 아닌 List를 이용합시다.

원형 연결리스트의 테스트 코드 작성

@Test
void CircularLinkedList의_생성_및_초기화() {
  List<Integer> list = new CircularLinkedList<>();

  assertThat(list).isNotNull();
}

@Test
void CircularLinkedList에_데이터_5개_저장() {
  List<Integer> list = new CircularLinkedList<>();
  list.insert(11);
  list.insert(11);
  list.insert(22);
  list.insert(22);
  list.insert(33);

  assertThat(list.size()).isEqualTo(5);
  assertThat(list.get(0)).isEqualTo(11);
  assertThat(list.get(1)).isEqualTo(11);
  assertThat(list.get(2)).isEqualTo(22);
  assertThat(list.get(3)).isEqualTo(22);
  assertThat(list.get(4)).isEqualTo(33);
  assertThat(list.get(5)).isEqualTo(11);
}

@Test
void CircularLinkedList에_데이터_5개_저장_후_22인_데이터_모두_삭제() {
  List<Integer> list = new CircularLinkedList<>();
  list.insert(11);
  list.insert(11);
  list.insert(22);
  list.insert(22);
  list.insert(33);

  // Iterable을 구현하면 enhanced for loop를 사용할 수 있습니다.
  for (int i = 0; i < list.size(); i++) {
    if (list.get(i) == 22) {
      list.remove(i);
      i--; // 삭제되면 index가 조정되므로 해당 index부터 다시 확인해야 합니다.
    }
  }

  assertThat(list.size()).isEqualTo(3);
  assertThat(list.get(0)).isEqualTo(11);
  assertThat(list.get(1)).isEqualTo(11);
  assertThat(list.get(2)).isEqualTo(33);
  assertThat(list.get(3)).isEqualTo(11);
}

@Test
@DisplayName("CircularLinkedList 에러처리 확인")
void CircularLinkedList_에러처리_확인() {
  List<Integer> list = new CircularLinkedList<>();

  assertThat(list.get(3)).isNull();
  assertThat(list.remove(4)).isNull();
  assertThat(list.contains(null)).isFalse();
  assertThat(list.size()).isZero();
  assertThat(list.isEmpty()).isTrue();
}

@Test
@DisplayName("CircularLinkedList 에러처리 확인2")
void CircularLinkedList_에러처리_확인2() {
  List<Integer> list = new CircularLinkedList<>();

  list.insert(1);

  assertThat(list.get(3)).isEqualTo(1);
  assertThat(list.contains(null)).isFalse();
  assertThat(list.remove(4)).isEqualTo(1);
  assertThat(list.size()).isZero();
  assertThat(list.isEmpty()).isTrue();
}

크게 달라진 부분은 없습니다. 그냥 인덱스보다 큰 값에 접근 가능한지 확인하는 코드가 추가되었습니다.

원형 연결 리스트의 구현1: 리스트의 초기화와 노드의 삽입

일단 대략적인 구성입니다.

CircularLinkedList.java

package list;

public class CircularLinkedList<E> implements List<E> {

  private Node<E> tail;
  private int size;

  @Override
  public void insert(E data) {

  }

  @Override
  public int size() {
    return this.size;
  }

  @Override
  public boolean isEmpty() {
    return this.size == 0;
  }

  @Override
  public boolean contains(Object o) {
    return false;
  }

  @Override
  public E get(int index) {
    return null;
  }

  @Override
  public E remove(int index) {
    return null;
  }

  private static class Node<T> {

    private T data;
    private Node<T> next;

    public Node(T data) {
      this.data = data;
    }
  }
}

이젠 좀 익숙해지셨을 법한 코드입니다.

size 메소드와, isEmpty 메소드는 확인 가능하므로 추가해주었습니다.

Node를 가지고 있고, Node는 간단한 단방향 노드입니다.

List에서 특이한 점은 tail Node를 가지고 있다는 점입니다.

삽입 부분 구현

@Override
public void insert(E data) { // 의도는 tail 위치에 새로운 노드를 추가하는 것입니다.
  Node<E> newNode = new Node<>(data);
  if (this.tail == null) {
    newNode.next = newNode;
  } else {
    newNode.next = this.tail.next; // 새로 추가될 노드의 다음 노드가 기존의 첫번째 노드여야 합니다.
    this.tail.next = newNode; // 마지막 노드의 다음 노드가 새로 추가될 노드여야 합니다.
  }
  this.tail = newNode; // 마지막 노드는 새로 추가된 노드여야 합니다.
  size++;
}

추가할 때, tail이 null이면 tail에 추가한다는 점과, 다음 노드도 자기 자신을 reference함을 알 수 있습니다.

tail 위치에 데이터가 추가되는 일반적인 방식을 채택하여 원형 구조는 유지하며 tail이 참조하는 node의 refernce만 변경한 것을 볼 수 있습니다.

그림을 그려야 이해가 더 잘가는 듯 합니다.

원형 연결 리스트의 구현2: 데이터 조회

조회부분 구현

@Override
public boolean contains(Object o) {
  if (this.tail == null) { // 초기화만 된 상태라면 데이터가 없으므로 false를 반환합니다.
    return false;
  }
  Node<E> cur = this.tail.next; // head를 선택합니다.
  if (o == null) {
    for (int i = 0; i < this.size; i++) { // 사이즈만큼만 순회하도록 합니다.
      if (cur.data == null) {
        return true;
      }
      cur = cur.next;
    }
  } else {
    for (int i = 0; i < this.size; i++) {
      if (o.equals(cur.data)) {
        return true;
      }
      cur = cur.next;
    }
  }
  return false;
}

@Override
public E get(int index) {
  if (this.tail == null) {
    return null;
  }
  Node<E> cur = this.tail.next;
  for (int i = 0; i < index; i++) {
    cur = cur.next;
  }
  return cur.data;
}

조회는 tail이 존재할 경우 tail.next부터 조회합니다. 따라서 head부터 조회됨을 알 수 있습니다.

예외처리에 조금 신경을 썼습니다. tail이 null일 경우 아직 아무런 데이터도 입력되지 않았음을 알 수 있습니다.

그리고 contains는 while 루프를 사용할 경우 무한루프에 빠질 수 있으므로 size 만큼만 확인하도록 합니다.

원형 연결 리스트의 구현3: 노드의 삭제

노드의 삭제 또한 연결 리스트와 별 다른점은 없습니다.

다만 주의해야할 점은 tail Node가 dummy Node 형태가 아니기 떄문에 항상 null 체크를 해주어야 한다는 점이 있습니다.

그리고 tail Node를 통해 삭제를 수행하기 때문에 tail Node가 삭제되어야 하는 경우 문제가 될 수 있습니다. 그래서 조건문으로 처리해줍니다.

또, 마지막 남은 노드일 경우 삭제가 되면 초기상태로 되돌아가야 하기 때문에 이를 신경써줍니다.

삭제부분 구현

@Override
public E remove(int index) {
  if (this.tail == null) {
    return null;
  }
  Node<E> cur = this.tail.next;
  Node<E> prev = this.tail;

  for (int i = 0; i < index; i++) { // 삭제 대상까지 이동합니다.
    prev = cur;
    cur = cur.next;
  }

  if (cur == this.tail) { // 삭제 대상이 tail 노드라면
    if (this.tail == this.tail.next) { // 삭제 대상이 마지막 노드라면
      tail = null;
    } else {
      this.tail = prev;
    }
  }

  prev.next = cur.next; // 이전 노드의 다음 노드를 삭제할 노드의 다음 노드로 지정
  this.size--;
  return cur.data;
}

양방향 연결 리스트

양방향 연결 리스트는 오히려 구현이 간단해지는 느낌이 있습니다.

전 후 참조를 모두 가지고 있다보니 구현에 있어서 더 편할 수도 있습니다.

테스트 코드 작성

@Test
@DisplayName("DoublyLinkedList의 생성 및 초기화 테스트")
void DoublyLinkedList의_생성_및_초기화_테스트() {
  List<Integer> list = new DoublyLinkedList<>();

  assertThat(list).isNotNull();
}

@Test
@DisplayName("DoublyLinkedList 데이터 3개 저장 테스트")
void DoublyLinkedList_데이터_3개_저장_테스트() {
  List<Integer> list = new DoublyLinkedList<>();

  list.insert(11);
  list.insert(22);
  list.insert(33);

  assertThat(list.isEmpty()).isFalse();
  assertThat(list.size()).isEqualTo(3);
  assertThat(list.contains(11)).isTrue();
  assertThat(list.contains(22)).isTrue();
  assertThat(list.contains(33)).isTrue();
  assertThat(list.contains(44)).isFalse();
  assertThat(list.get(0)).isEqualTo(33);
  assertThat(list.get(1)).isEqualTo(22);
  assertThat(list.get(2)).isEqualTo(11);
}

@Test
@DisplayName("DoublyLinkedList 데이터 3개 저장 후 삭제 테스트")
void DoublyLinkedList_데이터_3개_저장_후_삭제_테스트() {
  List<Integer> list = new DoublyLinkedList<>();

  list.insert(11);
  list.insert(22);
  list.insert(33);

  list.remove(2);
  list.remove(1);

  assertThat(list.isEmpty()).isFalse();
  assertThat(list.size()).isEqualTo(1);
  assertThat(list.contains(11)).isFalse();
  assertThat(list.contains(22)).isFalse();
  assertThat(list.contains(33)).isTrue();
  assertThat(list.contains(44)).isFalse();
  assertThat(list.get(0)).isEqualTo(33);
}

@Test
@DisplayName("DoublyLinkedList 예외 처리 테스트")
void DoublyLinkedList_예외_처리_테스트() {
  List<Integer> list = new DoublyLinkedList<>();

  assertThat(list.get(3)).isNull();
  assertThat(list.remove(4)).isNull();
  assertThat(list.contains(null)).isFalse();
  assertThat(list.size()).isZero();
  assertThat(list.isEmpty()).isTrue();
}

@Test
@DisplayName("DoublyLinkedList 예외 처리 테스트2")
void DoublyLinkedList_예외_처리_테스트2() {
  List<Integer> list = new DoublyLinkedList<>();

  list.insert(1);

  assertThat(list.get(3)).isNull();
  assertThat(list.remove(4)).isNull();
  assertThat(list.contains(null)).isFalse();
  assertThat(list.size()).isEqualTo(1);
  assertThat(list.isEmpty()).isFalse();
}

테스트 코드를 먼저 작성합니다.

기본적인 구현 코드 작성

DoublyLinkedList.java

package list;

public class DoublyLinkedList<E> implements List<E> {

  private Node<E> head;
  private int size;

  @Override
  public void insert(E data) {

  }

  @Override
  public int size() {
    return this.size;
  }

  @Override
  public boolean isEmpty() {
    return this.size == 0;
  }

  @Override
  public boolean contains(Object o) {
    return false;
  }

  @Override
  public E get(int index) {
    return null;
  }

  @Override
  public E remove(int index) {
    return null;
  }

  private static class Node<E> {

    private E data;
    private Node<E> prev;
    private Node<E> next;

    public Node(E data) {
      this.data = data;
    }
  }
}

역시 이전 구현들과 다를건 거의 없고, Node의 구성이 prev가 추가되었음을 알 수 있습니다.

양뱡향 연결 리스트의 구현1: 노드의 삽입

노드를 삽입하는 것도 별반 차이가 없습니다.

Dummy 노드가 없음에 주의하며 구현합니다.

@Override
public void insert(E data) {
  Node<E> newNode = new Node<>(data);

  if (head != null) { // head가 존재한다면
    newNode.next = head; // 새로운 노드의 다음노드가 기존의 head노드
    this.head.prev = newNode; // 기존 head노드의 이전노드가 새로운 노드
  }

  this.head = newNode;
  this.size++;
}

양방향 연결 리스트의 구현2: 데이터 조회

@Override
public boolean contains(Object o) {
  if (this.head == null) {
    return false;
  }
  Node<E> cur = this.head;
  if (o == null) {
    if (cur.data == null) {
      return true;
    }
    while (cur.next != null) {
      cur = cur.next;
      if (cur.data == null) {
        return true;
      }
    }
  } else {
    if (o.equals(cur.data)) {
      return true;
    }
    while (cur.next != null) {
      cur = cur.next;
      if (o.equals(cur.data)) {
        return true;
      }
    }
  }
  return false;
}

@Override
public E get(int index) {
  if (this.head == null) {
    return null;
  }
  Node<E> cur = this.head;

  for (int i = 0; i < index; i++) {
    if (cur.next == null) {
      return null;
    }
    cur = cur.next;
  }

  return cur.data;
}

더미노드가 없음으로 인해서 중복되는 로직이 contains에 많이 보입니다.

반면 get의 구현은 간단합니다. 순차탐색을 수행하면 됩니다.

사실 역방향 탐색도 넣어보려고 했는데, tail 노드가 없어서 불가능하다고 생각이 되어서 포기했습니다.

책에는 없는 데이터 제거

@Override
public E remove(int index) {
  if (this.head == null) {
    return null;
  }
  Node<E> cur = this.head;

  for (int i = 0; i < index; i++) {
    if (cur.next == null) {
      return null;
    }
    cur = cur.next;
  }

  if (cur == this.head) { // head인 경우엔 prev가 존재하지 않으므로 지정할 수 없음
    this.head = cur.next;
    cur.next.prev = cur.prev;
  } else if (cur.next == null) { // tail인 경우엔 next가 존재하지 않으므로 지정할 수 없음
    cur.prev.next = cur.next;
  } else {
    cur.prev.next = cur.next;
    cur.next.prev = cur.prev;
  }

  this.size--;
  return cur.data;
}

조건이 조금 더럽게 되는데 이 역시 dummy노드가 없어서지 않을까 추측해봅니다.

다음은 Dummy Node를 넣어서 구현합니다.

Dummy노드를 추가한 Doubly Linked List의 구현

테스트 코드 작성

@Test
@DisplayName("DummyDoublyLinkedList의 생성 및 초기화 테스트")
void DummyDoublyLinkedList의_생성_및_초기화_테스트() {
  List<Integer> list = new DummyDoublyLinkedList<>();

  assertThat(list).isNotNull();
}

@Test
@DisplayName("DummyDoublyLinkedList 데이터 3개 저장 테스트")
void DummyDoublyLinkedList_데이터_3개_저장_테스트() {
  List<Integer> list = new DummyDoublyLinkedList<>();

  list.insert(11);
  list.insert(22);
  list.insert(33);

  assertThat(list.isEmpty()).isFalse();
  assertThat(list.size()).isEqualTo(3);
  assertThat(list.contains(11)).isTrue();
  assertThat(list.contains(22)).isTrue();
  assertThat(list.contains(33)).isTrue();
  assertThat(list.contains(44)).isFalse();
  assertThat(list.get(0)).isEqualTo(11);
  assertThat(list.get(1)).isEqualTo(22);
  assertThat(list.get(2)).isEqualTo(33);
}

@Test
@DisplayName("DummyDoublyLinkedList 데이터 3개 저장 후 삭제 테스트")
void DummyDoublyLinkedList_데이터_3개_저장_후_삭제_테스트() {
  List<Integer> list = new DummyDoublyLinkedList<>();

  list.insert(11);
  list.insert(22);
  list.insert(33);

  list.remove(2);
  list.remove(1);

  assertThat(list.isEmpty()).isFalse();
  assertThat(list.size()).isEqualTo(1);
  assertThat(list.contains(11)).isTrue();
  assertThat(list.contains(22)).isFalse();
  assertThat(list.contains(33)).isFalse();
  assertThat(list.contains(44)).isFalse();
  assertThat(list.get(0)).isEqualTo(11);
}

@Test
@DisplayName("DummyDoublyLinkedList 예외 처리 테스트")
void DummyDoublyLinkedList_예외_처리_테스트() {
  List<Integer> list = new DummyDoublyLinkedList<>();

  assertThat(list.get(3)).isNull();
  assertThat(list.remove(4)).isNull();
  assertThat(list.contains(null)).isFalse();
  assertThat(list.size()).isZero();
  assertThat(list.isEmpty()).isTrue();
}

@Test
@DisplayName("DummyDoublyLinkedList 예외 처리 테스트2")
void DummyDoublyLinkedList_예외_처리_테스트2() {
  List<Integer> list = new DummyDoublyLinkedList<>();

  list.insert(1);

  assertThat(list.get(3)).isNull();
  assertThat(list.remove(4)).isNull();
  assertThat(list.contains(null)).isFalse();
  assertThat(list.size()).isEqualTo(1);
  assertThat(list.isEmpty()).isFalse();
}

리스트 기본 형태 초기화

DummyDoublyLinkedList.java

public class DummyDoublyLinkedList<E> implements List<E> {

  private int size;
  private Node<E> head;
  private Node<E> tail;

  public DummyDoublyLinkedList() { // 초기화
    head = new Node<>(null);
    tail = new Node<>(null);
    head.next = tail;
    tail.prev = head;
  }

  @Override
  public void insert(E data) {

  }

  @Override
  public int size() {
    return this.size;
  }

  @Override
  public boolean isEmpty() {
    return this.size == 0;
  }

  @Override
  public boolean contains(Object o) {
    return false;
  }

  @Override
  public E get(int index) {
    return null;
  }

  @Override
  public E remove(int index) {
    return null;
  }

  private static class Node<T> {

    private T data;
    private Node<T> next;
    private Node<T> prev;

    public Node(T data) {
      this.data = data;
    }
  }
}

dummy Node를 추가하고, 이들끼리 서로를 알 수 있도록 하였습니다.

리스트에 노드 추가

@Override
public void insert(E data) { // tail쪽으로 데이터가 추가 됩니다.
  Node<E> newNode = new Node<>(data);

  newNode.prev = this.tail.prev; // 새로운 노드의 이전 노드는 마지막 노드입니다.
  newNode.next = this.tail; // 새로운 노드의 다음 노드는 tail입니다.
  this.tail.prev.next = newNode; // 이전 마지막 노드의 다음을 새로운 노드로 지정합니다.
  this.tail.prev = newNode; // tail 노드의 이전노드를 새로운 노드로 지정합니다.

  this.size++;
}

더미노드를 통해 복잡한 추가로직이 간단하게 변했습니다.

항상 코드를 작성하면, 이를 검증하도록 합시다.

리스트의 데이터 조회

@Override
public boolean contains(Object o) {
  if (o == null) {
    Node<E> cur = this.head.next;

    while(cur.next != null) {
      if (cur.data == null) {
        return true;
      }
      cur = cur.next;
    }

    return false;
  } else {
    Node<E> cur = this.head.next;

    while(cur.next != null) {
      if (o.equals(cur.data)) {
        return true;
      }
      cur = cur.next;
    }

    return false;
  }
}

@Override
public E get(int index) {
  if (isEmpty()) {
    return null;
  }

  Node<E> cur;

  // 절반을 나눠서 가까운 부분에서 접근하도록 합니다.
  if (index < (this.size / 2) + 1) { // 중간 값보다 작은 경우 앞에서부터 탐색합니다.
    cur = this.head.next;

    for (int i = 0; i < index; i++) {
      if (cur.next == null) {
        return null;
      }
      cur = cur.next;
    }
  } else {
    cur = this.tail;
    int reversedIndex = this.size - index;

    for (int i = 0; i < reversedIndex; i++) {
      if (cur.prev == null) {
        return null;
      }
      cur = cur.prev;
    }
  }

  return cur.data;
}

contains의 로직이 간단해진 것을 볼 수 있습니다.

get은 tail node가 추가되어 속도 개선을 위해 if문으로 분기한 차이가 있을 뿐, 로직은 동일합니다.

리스트의 데이터 제거

@Override
public E remove(int index) {
  if (isEmpty()) {
    return null;
  }

  Node<E> cur;

  // 절반을 나눠서 가까운 부분에서 접근하도록 합니다.
  if (index < (this.size / 2) + 1) { // 중간 값보다 작은 경우 앞에서부터 탐색합니다.
    cur = this.head.next;

    for (int i = 0; i < index; i++) {
      if (cur.next == null) {
        return null;
      }
      cur = cur.next;
    }
  } else {
    cur = this.tail;
    int reversedIndex = this.size - index;

    if (reversedIndex < 1) { // 현재 조회 가능한 index보다 조회한 index가 큰 경우
      return null;
    }
    for (int i = 0; i < reversedIndex; i++) {
      if (cur.prev == null) {
        return null;
      }
      cur = cur.prev;
    }
  }
  cur.prev.next = cur.next;
  cur.next.prev = cur.prev;
  this.size--;

  return cur.data;
}

거의 구현에만 집중했던 것 같습니다.

스택(Stack)

스택의 이해와 ADT 정의

스택(Stack)의 이해

스택은 쌓여진 접시를 생각하라고 하는 얘기도 있는데 여기선 특이하게 초코볼 통을 예로 들었네요.

먼저 들어간 것이 나중에 나온다, 후입선출, LIFO 의 특징을 가진 자료구조 입니다.

개념은 쉬워요. 하지만 책에서 나오다시피 활용하는게 어려운 것 같습니다.

스택 ADT의 정의

push(넣고), pop(꺼내고), peek(확인하고)의 세동작으로 대표되는 자료구조입니다.

그래서 스택의 대표적인 동작을 위의 세 개로 정의할 수 있겠죠.

나머지는 스택 자료구조를 활용하기 위한 보조적인 동작이라고 생각하면 될 것 같습니다.

Stack.java

package stack;

/**
 * 스택 자료구조의 ADT, 인터페이스
 *
 * @param <E> 데이터의 파라미터 타입
 * @author dion
 */
public interface Stack<E> {

  /**
   * 스택에 저장된 데이터의 개수를 반환합니다.
   *
   * @return 데이터의 개수
   */
  int size();

  /**
   * 스택이 비어있는지 여부를 반환합니다.
   *
   * @return 스택이 비어있으면 true, 그렇지 않으면 false
   */
  boolean isEmpty();

  /**
   * 스택에 파라미터로 전달된 데이터를 마지막에 저장합니다.
   *
   * @param data 저장할 데이터
   */
  void push(E data);

  /**
   * 스택의 마지막에 위치한 데이터를 꺼냅니다. 이 함수를 호출하기 위해서는 데이터가 하나 이상 있음이 보장되어야 합니다.
   *
   * @return 마지막에 위치했던 데이터
   */
  E pop();

  /**
   * 스택의 마지막에 위치한 데이터를 확인합니다. 이 함수를 호출하기 위해서는 데이터가 하나 이상 있음이 보장되어야 합니다.
   *
   * @return 마지막에 위치한 데이터
   */
  E peek();
}

갑자기 삘받아서 javadoc도 작성해보았습니다.

보통 인터페이스의 경우에는 거의 필수적으로 javadoc으로 문서화를 해줘야 하는 것 같습니다.

스택은 배열과 연결 리스트로 구현할 수 있는데, 저는 연결리스트밖에 안해봤네요.

여튼 스택과 큐를 넘어서면, 선형 자료구조는 끝이나게 되니 힘을 내봅시다.

스택의 배열 기반 구현

구현의 논리와 헤더파일의 정의

일단 시작 인덱스가 -1이네요. 그리고 데이터는 0번부터 추가됨을 알 수 있습니다.

배열 기반 스택의 push와 pop 연산

  • push top index를 증가시키고, 해당하는 위치에 데이터를 넣습니다.
  • pop top 위치에 있는 데이터를 반환하고, top 인덱스를 내립니다. (null로 초기화해줘야 참조가 사라집니다. → 덮어씌워지기 때문에 그대로 두어도 무방합니다.)

테스트 코드 작성

StackTest.java

class StackTest {

  @Test
  @DisplayName("Array Stack의 생성 및 초기화")
  void arrayStack의_생성_및_초기화() {
    Stack<Integer> stack = new ArrayStack<>();

    assertThat(stack).isNotNull();
    assertThat(stack.isEmpty()).isTrue();
    assertThat(stack.size()).isEqualTo(0);
  }

  @Test
  @DisplayName("Array Stack의 EmptyStackException 테스트")
  void arrayStack의_EmptyStackException_테스트() {
    Stack<Integer> stack = new ArrayStack<>();

    assertThat(stack).isNotNull();
    assertThat(stack.isEmpty()).isTrue();
    assertThat(stack.size()).isEqualTo(0);
    assertThatThrownBy(stack::pop).isInstanceOf(EmptyStackException.class);
    assertThatThrownBy(stack::peek).isInstanceOf(EmptyStackException.class);
  }

  @Test
  @DisplayName("Array Stack에 데이터 5개 넣기")
  void arrayStack에_데이터_5개_넣기() {
    Stack<Integer> stack = new ArrayStack<>();

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);

    assertThat(stack).isNotNull();
    assertThat(stack.isEmpty()).isFalse();
    assertThat(stack.size()).isEqualTo(5);
  }

  @Test
  @DisplayName("Array Stack에 데이터 5개 넣고 뺴기")
  void arrayStack에_데이터_5개_넣고_빼기() {
    Stack<Integer> stack = new ArrayStack<>();

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);

    assertThat(stack).isNotNull();
    assertThat(stack.isEmpty()).isFalse();
    assertThat(stack.size()).isEqualTo(5);
    assertThat(stack.peek()).isEqualTo(5);
    assertThat(stack.pop()).isEqualTo(5);
    assertThat(stack.peek()).isEqualTo(4);
    assertThat(stack.pop()).isEqualTo(4);
    assertThat(stack.peek()).isEqualTo(3);
    assertThat(stack.pop()).isEqualTo(3);
    assertThat(stack.peek()).isEqualTo(2);
    assertThat(stack.pop()).isEqualTo(2);
    assertThat(stack.peek()).isEqualTo(1);
    assertThat(stack.pop()).isEqualTo(1);
    assertThat(stack.isEmpty()).isTrue();
    assertThat(stack.size()).isEqualTo(0);
  }
}

테스트 코드부터 작성해보았습니다.

책의 구성이 자꾸 Main이 뒤에 있어서 테스트 코드 짜는걸 깜빡하게되네요..

배열 기반의 스택 기본형태, 초기화 코드 작성

ArrayStack.java

public class ArrayStack<E> implements Stack<E> {

  private static final int INITIAL_CAPACITY = 100;

  private int topIndex;
  private Object[] arr;

  public ArrayStack() {
    this.topIndex = -1;
    this.arr = new Object[INITIAL_CAPACITY];
  }

  @Override
  public int size() {
    return this.topIndex + 1;
  }

  @Override
  public boolean isEmpty() {
    return this.topIndex == -1;
  }

  @Override
  public void push(E data) {

  }

  @Override
  public E pop() {
    return null;
  }

  @Override
  public E peek() {
    return null;
  }
}

초기화 할 때, 기본적으로 지정되어 있는 크기를 사용하도록 하였습니다.

topIndex는 위에서 설명한 top 위치를 얘기합니다. 기본값으로 -1을 가지고 생성되도록 하였습니다.

size나 isEmpty가 topIndex를 기반으로 하는 것을 제외하면, ArrayList와 큰 차이는 없습니다.

push, pop, peek만 채우면 되겠군요!

push, pop, peek 메소드 구현

@Override
public void push(E data) {
  this.topIndex++;
  arr[topIndex] = data;
}

@Override
public E pop() {
  if (isEmpty()) {
    throw new EmptyStackException();
  }
  this.topIndex--;
  return (E) arr[topIndex + 1];
}

@Override
public E peek() {
  if (isEmpty()) {
    throw new EmptyStackException();
  }
  return (E) arr[topIndex];
}

topIndex를 적절히 조정해가면, 간단하게 구현할 수 있습니다.

스택의 연결 리스트 기반 구현

ADT는 동일하므로 넘어가고, 이전과 같은 테스트 코드를 작성하면 될 것 같습니다.

@Test
@DisplayName("List Stack의 생성 및 초기화")
void listStack의_생성_및_초기화() {
  Stack<Integer> stack = new ListStack<>();

  assertThat(stack).isNotNull();
  assertThat(stack.isEmpty()).isTrue();
  assertThat(stack.size()).isEqualTo(0);
}

@Test
@DisplayName("List Stack의 EmptyStackException 테스트")
void listStack의_EmptyStackException_테스트() {
  Stack<Integer> stack = new ListStack<>();

  assertThat(stack).isNotNull();
  assertThat(stack.isEmpty()).isTrue();
  assertThat(stack.size()).isEqualTo(0);
  assertThatThrownBy(stack::pop).isInstanceOf(EmptyStackException.class);
  assertThatThrownBy(stack::peek).isInstanceOf(EmptyStackException.class);
}

@Test
@DisplayName("List Stack에 데이터 5개 넣기")
void listStack에_데이터_5개_넣기() {
  Stack<Integer> stack = new ListStack<>();

  stack.push(1);
  stack.push(2);
  stack.push(3);
  stack.push(4);
  stack.push(5);

  assertThat(stack).isNotNull();
  assertThat(stack.isEmpty()).isFalse();
  assertThat(stack.size()).isEqualTo(5);
}

@Test
@DisplayName("List Stack에 데이터 5개 넣고 뺴기")
void listStack에_데이터_5개_넣고_빼기() {
  Stack<Integer> stack = new ListStack<>();

  stack.push(1);
  stack.push(2);
  stack.push(3);
  stack.push(4);
  stack.push(5);

  assertThat(stack).isNotNull();
  assertThat(stack.isEmpty()).isFalse();
  assertThat(stack.size()).isEqualTo(5);
  assertThat(stack.peek()).isEqualTo(5);
  assertThat(stack.pop()).isEqualTo(5);
  assertThat(stack.peek()).isEqualTo(4);
  assertThat(stack.pop()).isEqualTo(4);
  assertThat(stack.peek()).isEqualTo(3);
  assertThat(stack.pop()).isEqualTo(3);
  assertThat(stack.peek()).isEqualTo(2);
  assertThat(stack.pop()).isEqualTo(2);
  assertThat(stack.peek()).isEqualTo(1);
  assertThat(stack.pop()).isEqualTo(1);
  assertThat(stack.isEmpty()).isTrue();
  assertThat(stack.size()).isEqualTo(0);
}

이전 테스트 코드와 달라진 점은 딱 클래스 선언 부분 말고는 달라지지 않았습니다.

리스트 기반의 스택 기본 형태, 초기화 코드 작성

ListStack.java

public class ListStack<E> implements Stack<E> {

  private int size;
  private Node<E> head;

  @Override
  public int size() {
    return this.size;
  }

  @Override
  public boolean isEmpty() {
    return this.size == 0;
  }

  @Override
  public void push(E data) {

  }

  @Override
  public E pop() {
    return null;
  }

  @Override
  public E peek() {
    return null;
  }

  private static class Node<T> {

    private T data;
    private Node<T> next;

    public Node(T data) {
      this.data = data;
    }
  }
}

LinkedList의 형태랑 똑같습니다.

다른 점이 있다면, 제공하는 인터페이스가 다르다는 점 뿐이죠.

리스트 기반의 스택, push, pop, peek 메소드 구현

head 부분만 리스트가 가지고 있기 때문에 당연히 push는 head쪽으로 수행되어야 합니다.

pop을 할 때도 마찬가지 입니다.

배열기반과 마찬가지로 pop과 peek은 예외처리도 해줘야겠죠?

@Override
public void push(E data) {
  Node<E> newNode = new Node<>(data);
  newNode.next = this.head;
  this.head = newNode;
  this.size++;
}

@Override
public E pop() {
  if (isEmpty()) {
    throw new EmptyStackException();
  }
  Node<E> tmpNode = this.head;
  this.head = this.head.next;
  size--;
  return tmpNode.data;
}

@Override
public E peek() {
  if (isEmpty()) {
    throw new EmptyStackException();
  }
  return this.head.data;
}

스택 자체의 구현은 쉽게 끝났습니다.

하지만, 스택을 활용한 알고리즘 문제풀이는 구현보단 까다롭습니다. 다음은 계산기를 만들어 보는군요..

그 전에 원형 연결리스트를 활용해서 구현하는 것을 먼저해보겠습니다.

원형 연결 리스트 기반의 스택 테스트 코드 작성

@Test
@DisplayName("CircularList Stack의 생성 및 초기화")
void circularListStack의_생성_및_초기화() {
  Stack<Integer> stack = new CircularListStack<>();

  assertThat(stack).isNotNull();
  assertThat(stack.isEmpty()).isTrue();
  assertThat(stack.size()).isEqualTo(0);
}

@Test
@DisplayName("CircularList Stack의 EmptyStackException 테스트")
void circularListStack의_EmptyStackException_테스트() {
  Stack<Integer> stack = new CircularListStack<>();

  assertThat(stack).isNotNull();
  assertThat(stack.isEmpty()).isTrue();
  assertThat(stack.size()).isEqualTo(0);
  assertThatThrownBy(stack::pop).isInstanceOf(EmptyStackException.class);
  assertThatThrownBy(stack::peek).isInstanceOf(EmptyStackException.class);
}

@Test
@DisplayName("CircularList Stack에 데이터 5개 넣기")
void circularListStack에_데이터_5개_넣기() {
  Stack<Integer> stack = new CircularListStack<>();

  stack.push(1);
  stack.push(2);
  stack.push(3);
  stack.push(4);
  stack.push(5);

  assertThat(stack).isNotNull();
  assertThat(stack.isEmpty()).isFalse();
  assertThat(stack.size()).isEqualTo(5);
}

@Test
@DisplayName("CircularList Stack에 데이터 5개 넣고 뺴기")
void circularListStack에_데이터_5개_넣고_빼기() {
  Stack<Integer> stack = new CircularListStack<>();

  stack.push(1);
  stack.push(2);
  stack.push(3);
  stack.push(4);
  stack.push(5);

  assertThat(stack).isNotNull();
  assertThat(stack.isEmpty()).isFalse();
  assertThat(stack.size()).isEqualTo(5);
  assertThat(stack.peek()).isEqualTo(5);
  assertThat(stack.pop()).isEqualTo(5);
  assertThat(stack.peek()).isEqualTo(4);
  assertThat(stack.pop()).isEqualTo(4);
  assertThat(stack.peek()).isEqualTo(3);
  assertThat(stack.pop()).isEqualTo(3);
  assertThat(stack.peek()).isEqualTo(2);
  assertThat(stack.pop()).isEqualTo(2);
  assertThat(stack.peek()).isEqualTo(1);
  assertThat(stack.pop()).isEqualTo(1);
  assertThat(stack.isEmpty()).isTrue();
  assertThat(stack.size()).isEqualTo(0);
}

구현하기

public class CircularListStack<E> implements Stack<E> {

  private final List<E> list = new CircularLinkedList<>();
  private int lastIndex = -1;

  @Override
  public int size() {
    return this.list.size();
  }

  @Override
  public boolean isEmpty() {
    return this.list.isEmpty();
  }

  @Override
  public void push(E data) {
    this.lastIndex++;
    this.list.insert(data);
  }

  @Override
  public E pop() {
    if (isEmpty()) {
      throw new EmptyStackException();
    }
    E tmpData = this.list.remove(lastIndex);
    this.lastIndex--;
    return tmpData;
  }

  @Override
  public E peek() {
    if (isEmpty()) {
      throw new EmptyStackException();
    }
    return this.list.get(lastIndex);
  }
}

초기화시에 빈 CircularLinkedList로 초기화되도록 하였습니다.

lastIndex를 둔 이유는, 제가 구현을 index 기반으로 가져오도록 하였기 때문입니다.

구현 자체는 크게 다를 것이 없고, list 인터페이스를 활용하였습니다.

계산기 프로그램 구현

알고리즘 코딩테스트에서도 꽤나 자주 등장하는 유형인 괄호가 나오는 계산입니다.

물론 코테에선 이보다 복잡한 유형의 문제들이 나옵니다... 😞

수식의 표기법: 중위(infix), 전위(prefix), 후위(postfix) 표기법

저도 몰랐던 내용들이네요. 중위 표기법이기 때문에 연산자 우선순위를 알아야하고, 소괄호를 씌워서 연산의 우선순위를 결정한다...

컴파일러도 연산을 후위 표기법으로 바꾸어서 한다는 내용도 처음들어봐서 좋았습니다.

중위 표기법을 후위 표기법으로 바꾸는 방법 1/2: 소괄호를 고려하지 않고

그림을 보면서 원리를 익히고 문제를 직접 풀어보셨다면 이해한 것 같습니다.

어차피 코드로 옮기려면 손으로 써보는 경험이 되게 중요한 것 같습니다.

실제로 Leet Code medium 난이도 문제를 푸는데도 그림을 그려서 푸니까 더 잘 풀리더라고요!

중위 표기법을 후위 표기법으로 바꾸는 방법 2/2: 소괄호를 고려하고

설명이 자세해서 제가 따로 부연설명할 점은 없는 것 같습니다.

책에 낚시 당해서 손으로 열심히 옮겨 적었는데, 다음장에 변환해 볼 필요 없다고... 🤯

중위 표기법을 후위 표기법으로 바꾸는 프로그램의 구현

  • 입력된 정보를 배열로 만들기
  • 전달된 중위 표기법 배열을 후위 표기법으로 바꾸는 함수
  • 연산자의 연산 우선순위 정보를 반환하는 함수
  • 연산자의 우선순위 정보를 바탕으로 그 결과를 반환하는 함수

중위 표기법을 후위 표기법으로 바꾸는 클래스의 테스트 코드 작성

InfixToPostfixTest.java

class InfixToPostfixTest {

  InfixToPostfix infixToPostfix;

  @BeforeEach
  void setUp() {
    infixToPostfix = new InfixToPostfix();
  }

  @Test
  @DisplayName("입력된 정보를 배열로 만드는지 테스트")
  void 입력된_정보를_배열로_만드는지_테스트() {
    String input = "1 + 2 * 3";
    char[] expected = {'1', '+', '2', '*', '3'};
    char[] actual = infixToPostfix.convertInputToCharArray(input);

    assertThat(actual).isNotEmpty().hasSameSizeAs(expected).containsExactly(expected);
  }

  @Test
  @DisplayName("중위 표기법 배열을 후위 표기법으로 바꾸는 함수 테스트1")
  void 중위_표기법_배열을_후위_표기법으로_바꾸는_함수_테스트1() {
    char[] input = {'1', '+', '2', '*', '3'}; // 123*+
    char[] expected = {'1', '2', '3', '*', '+'};
    char[] actual = infixToPostfix.convertInfixToPostfix(input);

    assertThat(actual).isNotEmpty().hasSameSizeAs(expected).containsExactly(expected);
  }

  @Test
  @DisplayName("중위 표기법 배열을 후위 표기법으로 바꾸는 함수 테스트2")
  void 중위_표기법_배열을_후위_표기법으로_바꾸는_함수_테스트2() {
    char[] input = {'(', '1', '*', '2', '+', '3', ')', '/', '4'}; // 12*3+4/
    char[] expected = {'1', '2', '*', '3', '+', '4', '/'};
    char[] actual = infixToPostfix.convertInfixToPostfix(input);

    assertThat(actual).isNotEmpty().hasSameSizeAs(expected).containsExactly(expected);
  }

  @Test
  @DisplayName("연산자의 연산 우선순위 정보를 반환하는 함수테스트")
  void 연산자의_연산_우선순위_정보를_반환하는_함수_테스트() {
    char multiplicationSign = '*';
    char divisionSign = '/';
    char plusSign = '+';
    char minusSign = '-';
    char openingParenthesis = '(';
    char noSign = ')';

    assertThat(getOperatorPriority(multiplicationSign)).isEqualTo(OperatorPriority.TOP);
    assertThat(getOperatorPriority(divisionSign)).isEqualTo(OperatorPriority.TOP);
    assertThat(getOperatorPriority(plusSign)).isEqualTo(OperatorPriority.MID);
    assertThat(getOperatorPriority(minusSign)).isEqualTo(OperatorPriority.MID);
    assertThat(getOperatorPriority(openingParenthesis)).isEqualTo(OperatorPriority.BOT);
    assertThat(getOperatorPriority(noSign)).isEqualTo(OperatorPriority.NONE);
  }

  @Test
  @DisplayName("연산자의 우선순위 정보를 바탕으로 그 결과를 반환하는 함수 테스트1")
  void 연산자의_우선순위_정보를_바탕으로_그_결과를_반환하는_함수_테스트1() {
    char op1 = '*';
    char op2 = '+';

    assertThat(infixToPostfix.compareOperator(op1, op2)).isGreaterThan(0);
  }

  @Test
  @DisplayName("연산자의 우선순위 정보를 바탕으로 그 결과를 반환하는 함수 테스트2")
  void 연산자의_우선순위_정보를_바탕으로_그_결과를_반환하는_함수_테스트2() {
    char op1 = '-';
    char op2 = '+';

    assertThat(infixToPostfix.compareOperator(op1, op2)).isEqualTo(0);
  }

  @Test
  @DisplayName("연산자의 우선순위 정보를 바탕으로 그 결과를 반환하는 함수 테스트3")
  void 연산자의_우선순위_정보를_바탕으로_그_결과를_반환하는_함수_테스트3() {
    char op1 = '(';
    char op2 = '+';

    assertThat(infixToPostfix.compareOperator(op1, op2)).isLessThan(0);
  }
}

테스트 코드에서 주의깊게 봐야할 점은 assertJ에서 메소드 체이닝으로 한 객체를 계속 검증했다는 점과

containsExactly를 하면 모두 검사한다는 점입니다.

중위 표기법을 후위 표기법으로 바꾸는 클래스 작성

OperatorPriority.java Enum으로 연산자 우선순위 선언

public enum OperatorPriority {
  TOP(3),
  MID(2),
  BOT(1),
  NONE(-1);

  private final int priority;

  OperatorPriority(int priority) {
    this.priority = priority;
  }

  public static OperatorPriority getOperatorPriority(char sign) {
    switch (sign) {
      case '*':
      case '/':
        return TOP;
      case '+':
      case '-':
        return MID;
      case '(':
        return BOT;
      default:
        return NONE;
    }
  }

  public int getPriority() {
    return priority;
  }
}

Enum을 사용한 이유는 숫자 상수를 남용하지 않기 위해서입니다.

이 과정에서 공부한 내용이 있는데요, Enum은 Compare 기준이 위에서 선언한 순서대로여서, 이 순서를 바꾸기 보다는, 개별 비교함수를 선언해주는게 나은 것 같습니다.

찾아보니 Comparator를 Enum에 선언하는 경우가 있었는데, 윤성우 자료구조를 따라가다보니 비교로직이 다른 클래스로 들어갔네요. 지양해야할 점 중 하나입니다.

InfixToPostfix.java

public class InfixToPostfix {

  public char[] convertInputToCharArray(String input) {
    return input.replace(" ", "").toCharArray();
  }

  public char[] convertInfixToPostfix(char[] infixCharArray) {
    Stack<Character> stack = new ListStack<>();
    char[] postfixCharArray = new char[infixCharArray.length];

    int idx = 0;
    for (char tok : infixCharArray) {
      if (Character.isDigit(tok)) { // tok이 숫자인지 확인
        postfixCharArray[idx++] = tok; // 숫자형이면 그대로 넣고, idx값을 증가시킨다.
      } else { // 연산자라면
        switch (tok) {
          case '(': // 여는 괄호라면
            stack.push(tok); // 스택에 넣는다.
            break;
          case ')': // 닫는 괄호라면
            while (true) { // 계속해서
              char popOp = stack.pop(); // 스택에서 연산자를 꺼낸다.
              if (popOp == '(') { // 연산자 (를 만날 때까지
                break;
              }
              postfixCharArray[idx++] = popOp; // 연산자를 배열에 넣는다.
            }
            break;
          case '+':
          case '-':
          case '*':
          case '/':
            // 사칙연산자가 들어오면, 스택이 비어있는지 확인하고, 스택이 비어있지 않다면, 맨 위의 연산자와 비교해서 스택에 있는 연산자가 연산을 먼저해야한다면
            while (!stack.isEmpty() && compareOperator(stack.peek(), tok) >= 0) {
              postfixCharArray[idx++] = stack.pop(); // 스택에서 연산자를 꺼내서 배열에 넣는다.
            }
            stack.push(tok); // 스택에 연산자를 넣는다.
            break;
        }
      }
    }
    while (!stack.isEmpty()) { // 스택에 남아있는 모든 연산자를 배열에 저장한다.
      postfixCharArray[idx++] = stack.pop();
    }

    return Arrays.copyOf(postfixCharArray, idx); // 후위 연산으로 변경되면 길이가 줄어들고, 배열의 길이는 idx값과 동일하므로
  }

  public int compareOperator(char op1, char op2) {
    OperatorPriority op1Priority = OperatorPriority.getOperatorPriority(op1);
    OperatorPriority op2Priority = OperatorPriority.getOperatorPriority(op2);
    return op1Priority.getPriority() - op2Priority.getPriority();
  }
}

비교하는 메서드가 여기 들어가있습니다. 뭔가 잘못된 느낌이 드네요. 이 방법도 나쁘진 않은 것 같습니다.

저 convertInfixToPostfix 코드는 매우 복잡합니다. 뭔가 굉장히 냄새나는 코든데, 딱히 책에서 리팩토링을 하지는 않네요.

같이 한 번 리팩토링 해보는 것도 좋을 것 같습니다. 굉장히 복잡해서 이해하기 어려운 메소드라고 생각해요.

후위 표기법으로 표현된 수식의 계산방법

첫번째 연산자 앞의 두 숫자가 연산 대상입니다.

연산자가 나오는 순서대로 계산하면 되는 것 같아요.

후위 표기법으로 표현된 수식을 계산하는 프로그램의 구현

  • 피연산자는 무조건 스택으로 옮긴다.
  • 연산자를 만나면 스택에서 두 개의 피연산자를 꺼내서 계산을 한다.
  • 계산 결과는 다시 스택에 넣는다.

후위 표기법으로 표현된 수식을 계산하는 클래스의 테스트 코드 작성

PostCalculatorTest.java

class PostCalculatorTest {

  PostCalculator postCalculator;

  @BeforeEach
  void setUp() {
    postCalculator = new PostCalculator();
  }

  @Test
  @DisplayName("후위_표기법으로_작성된_수식_계산_테스트1")
  void 후위_표기법으로_작성된_수식_계산_테스트1() {
    char[] input = {'4', '2', '*', '8', '+'};

    assertThat(postCalculator.calculate(input)).isEqualTo(16);
  }

  @Test
  @DisplayName("후위_표기법으로_작성된_수식_계산_테스트2")
  void 후위_표기법으로_작성된_수식_계산_테스트2() {
    char[] input = {'1', '2', '3', '+', '*', '4', '/'};

    assertThat(postCalculator.calculate(input)).isEqualTo(1);
  }
}

통합해서 테스트 하는 방법도 있을 수 있겠네요!

후위 표기법으로 표현된 수식을 계산하는 클래스 작성

PostCalculator.java

public class PostCalculator {

  public int calculate(char[] input) {
    Stack<Integer> stack = new ListStack<>();

    for (char tok : input) {
      if (Character.isDigit(tok)) {
        stack.push(Character.getNumericValue(tok));
      } else {
        int op2 = stack.pop();
        int op1 = stack.pop();

        switch (tok) {
          case '+':
            stack.push(op1 + op2);
            break;
          case '-':
            stack.push(op1 - op2);
            break;
          case '*':
            stack.push(op1 * op2);
            break;
          case '/':
            stack.push(op1 / op2);
            break;
        }
      }
    }

    return stack.pop();
  }
}

책에서 몇 가지 맘에 안드는 부분이 있어 수정했습니다.

Stack에는 사실 정수형만 담기게 되어있는데, 연산자라고 표현하기도 하고, char형으로 저장하더라고요.

C언어에서만 가능한 방법이라고 생각합니다.

foreach문을 써서 좀 더 아름답게 짜려고 했습니다.

여기서 제일 주의해야 할 점은 op2를 먼저 뽑고, op1을 뽑는다는 것 입니다.

이제 하나로 묶자!

간단히 말해서 중위 표기법으로 작성된 테스트 코드를 작성하고 동작함을 확인하면 됩니다. 참 쉽죠?

InfixCalculatorTest.java

class InfixCalculatorTest {

  InfixCalculator infixCalculator;

  @BeforeEach
  void setUp() {
    infixCalculator = new InfixCalculator();
  }

  @Test
  @DisplayName("중위_표기법으로_작성된_수식_계산_테스트1")
  void 중위_표기법으로_작성된_수식_계산_테스트1() {
    String input = "1 + 2 * 3";

    assertThat(infixCalculator.calculate(input)).isEqualTo(7);
  }

  @Test
  @DisplayName("중위_표기법으로_작성된_수식_계산_테스트2")
  void 중위_표기법으로_작성된_수식_계산_테스트2() {
    String input = "(1 + 2) * 3";

    assertThat(infixCalculator.calculate(input)).isEqualTo(9);
  }

  @Test
  @DisplayName("중위_표기법으로_작성된_수식_계산_테스트3")
  void 중위_표기법으로_작성된_수식_계산_테스트3() {
    String input = "((1 - 2) + 3) * (5 - 2)";

    assertThat(infixCalculator.calculate(input)).isEqualTo(6);
  }
}

테스트 코드는 간단합니다.

InfixToPostfix.java

public char[] convertInputToPostfix(String input) {
  return this.convertInfixToPostfix(this.convertInputToCharArray(input));
}

위의 메소드를 추가해서 외부에선 이 메소드만 참조하도록 합시다.

인터페이스를 사용해도 좋을 것 같아요.

InfixCalculator.java

public class InfixCalculator {

  InfixToPostfix infixToPostfix = new InfixToPostfix();
  PostCalculator postCalculator = new PostCalculator();

  public int calculate(String input) {
    return postCalculator.calculate(infixToPostfix.convertInputToPostfix(input));
  }
}

아까 구현을 다 해둬서 정말 간단하게 구현되었습니다.

이번주도 고생많으셨습니다!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment