더디지만... 꾸준히...

1. 개요 & 알고리즘

Queue는 put과 get 동작을 수행하합니다. 자료는 뒤(rear)에 집어 넣고, 앞(front)에서 자료를 얻어내는 FIFO(First Input First Output) 동작을 하는 자료구조입니다.("C로 배우는 알고리즘"^[각주:1]) Python에서는 자체적으로 Queue를 제공^[각주:2]합니다만, 앞선 Stack에 대한 포스팅에서와 마찬가지로 List와 Linked list를 이용해서 Queue를 구현해 보겠습니다.

2. 동작 코드

Python에서 List를 이용해서 Queue를 구현한다면, 다음과 같이도 구현할 수 있어 보입니다.

* get()의 경우, List의 0번째 element를 읽고, del()을 사용해서 0번째 element를 지웁니다^[각주:3]. 이 경우 뒤에 있는 element들이 모두 앞으로 한칸씩 전진합니다.

* put()의 경우, List의 append()를 사용합니다.

* Python은 메모리 제약이 없기 때문에, empty 경우에 대해서만 예외처리하면 됩니다.

하지만, "C로 배우는 알고리즘"에서 구현한대로 List를 이용해서 Circular 동작을 하도록 구현하는 것은 알고리즘을 이해하는데 도움이 될 것으로 생각됩니다.

front와 rear가 같은 경우 empty로 생각하면 되고, front와 rear 사이에는 완충지대를 1개 둡니다. 따라서 front가 rear+1이면 full로 생각합니다.

put()은 아래와 같이 구현합니다.

def put(self, data):
    if (self.rear + 1) % self.max_num_of_list == self.front:
        print("Queue overflow")
        return False
    self.queue[self.rear] = data
    self.rear = (self.rear + 1) % self.max_num_of_list

    return data

get()은 아래와 같이 구현합니다.

def get(self):
    if self.front == self.rear:
        print("Queue underflow")
        return False
    data = self.queue[self.front]
    self.front = (self.front + 1) % self.max_num_of_list

    return data

3. 실행 코드

실행 코드는 아래와 같습니다("C로 배우는 알고리즘" 리스트 3-12 : QUEUE1에 대응) Full인 상황과 empty인 상황도 시험하도록 합니다.

# main() function
if __name__ == "__main__":
    queue = QueueWithArray()
    queue.init_queue()

    print("Put 5, 4, 7, 8, 2, 1")
    queue.put(5)
    queue.put(4)
    queue.put(7)
    queue.put(8)
    queue.put(2)
    queue.put(1)
    queue.print_queue()

    print("Get")
    data = queue.get()
    queue.print_queue()
    print("Getting value is ", data)

    print("Put 3, 2, 5, 7")
    queue.put(3)
    queue.put(2)
    queue.put(5)
    queue.put(7)
    queue.print_queue()

    print("Now queue is full, put 3")
    queue.put(3)
    queue.print_queue()

    print("Initialize queue")
    queue.clear_queue()
    queue.print_queue()

    print("Now queue is empty, get")
    data = queue.get()
    queue.print_queue()
    print("Getting value is ", data)

4. 코드

1. 개요 & 알고리즘

앞선 포스팅^[각주:1]에서 Stack을 이용해서 중위 표기법(Infix notation)으로 표현된 수식을 입력으로 받아서 후위 표기법(Postfix notation)으로 변경했습니다. 이번 포스팅에서는 후위 표기법으로 표시된 수식을 Stack을 이용해서 계산합니다. ("C로 배우는 알고리즘"^[각주:2])

알고리즘은 다음과 같습니다.

1. 숫자를 만나면 숫자는 Stack에 push한다.

2. 연산자를 만나면 Stack에서 pop을 두 번하여 그 두 데이터를 가지고 연산한 다음 그 결과를 Stack에 다시 push한다.

답은 마지막으로 Stack에 남아있는 값이 됩니다.

2. 동작 코드

10 이상의 숫자를 입력 받아서 연산을 할 수도 있습니다. 이에 앞선 포스팅^[각주:3]과 달리 이 부분을 보완했습니다. ("C로 배우는 알고리즘"^[각주:4]에는 이미 있는 내용이었습니다.) 입력된 값에서 숫자가 연속되는 경우 (아래 코드에서는 is_num이 1인 경우)를 처리하기 위한 코드입니다. 숫자의 구분은 space로 합니다.

def do_postfix(self, source):
    dst = []
    stack = []
    is_num = 0
    for i in source:
        # To handle not only single digit but also more than 10
        if '0' <= i <= '9':
            if is_num == 1:
                dst[-1] = i
            else:
                dst.append(i)
            dst.append(' ')
            is_num = 1
            continue

        is_num = 0
        # 이하 생략

후위 표기법으로 Stack에 저장된 값을 읽어서 계산하는 루틴입니다. 숫자가 연속되는 경우 앞의 숫자에 10을 곱한 후 현재 숫자를 더하는 계산을 수행합니다. "C로 배우는 알고리즘"^[각주:5]에 적혀 있듯이 "눈여겨 볼만한 기법"입니다.

def do_calc(self, src):
    stack = []
    i = 0
    while i < len(src):
        ch = src[i]
        if '0' <= ch <= '9':
            t = 0
            while True:
                t = t * 10 + int(ch)
                if '0' <= src[i+1] <= '9':
                    i += 1
                    ch = src[i]
                else:
                    break
            stack.append(t)
        elif ch == '+':
            t = stack.pop() + stack.pop()
            stack.append(t)
        elif ch == '*':
            t = stack.pop() * stack.pop()
            stack.append(t)
        elif ch == '-':
            t = stack.pop()
            t = stack.pop() - t
            stack.append(t)
        elif ch == '/':
            t = stack.pop()
            t = stack.pop() / t
            stack.append(t)
        i += 1

    # Return results which is in stack
    return (stack.pop())

3. 실행 코드

실행 루틴은 다음과 같습니다.

# main() function
if __name__ == "__main__":
    source = input("Please input -> ")
    postfix = Postfix()
    # Change infix notation to postfix notation
    contents = postfix.do_postfix(source)
    # Evaluate expression
    results = postfix.do_calc(contents)
    # Print results
    print(results)

4. 코드

"C로 배우는 알고리즘" 리스트 3-11 : CALC.C에 해당합니다.

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_03/Ch_03_12.py

1. 개요 & 알고리즘

일반적으로 사용하는 중위 표기법(Infix notation)으로 표현된 수식을 입력으로 받아서 후위 표기법(Postfix notation)으로 바꾸고, 스택을 이용해서 값을 연산하여 화면에 출력하는 간단한 유틸리티인 CALC를 작성해 봅니다.("C로 배우는 알고리즘"^[각주:1])

후위 표기법으로의 변환은 책만 읽어서는 쉽게 이해되지 않습니다만, 인터넷에는 그림과 더불어 알기 쉽게 설명한 페이지^[각주:2]들이 많으니, 이를 참고하고 따로 설명은 하지 않겠습니다.

후위 표기법을 이용하면 괄호를 사용하지 않아도 되며, 스택의 push, pop 동작으로 수식을 evaluation할 수 있습니다.

이번 페이지에서는 스택을 이용해서 중위 표기법을 후위 표기법으로 변환하도록 하겠습니다. 우선 '(' 연산자는 제알 낮은 우선순위인 0을 주고, +와 - 연산자느 1의 우선순위를 *와 /는 2의 우선순위를 주겠습니다.

알고리즘은 다음과 같습니다.("C로 배우는 알고리즘"^[각주:3])

1. '('를 만나면 스택에 push한다.

2. ')'를 만나면 스택에서 '('가 나올 때까지 pop하여 출력하고 '('는 pop하여 버린다.

3. 연산자를 만나면 스택에서 그 연산자보다 낮은 우선순위의 연산자를 만날 때까지 팝하여 출력한 뒤에 자신을 push한다.

4. 피연산자는 그냥 출력한다.

5. 모든 입력이 끝나면 스택에 있는 연산자들을 모두 pop하여 출력한다.

2. 동작 코드

 기본적인 동작 코드는 다음과 같습니다.

def do_postfix(self, source):
    dst = []
    stack = []
    for i in source:
        if i == '(':
            stack.append(i)
        elif i == ')':
            while stack[-1] != '(':
                t = stack.pop()
                dst.append(t)
            stack.pop()
        elif self.is_operator(i):
            while len(stack) != 0 and self.precedence(stack[-1]) >= self.precedence(i):
                dst.append(stack.pop())
            stack.append(i)
        elif '0' <= i <= '9':
            dst.append(i)

    while len(stack) != 0:
        t = stack.pop()
        dst.append(t)

    return(dst)

3. 실행 코드

사용자로부터 중위 표기법으로 수식을 입력 받아서, 후위 표기법으로 출력하는 실행 코드입니다.

#main() function
if __name__ == "__main__":
    source = input("Please input -> ")
    postfix = Postfix()
    contents = postfix.do_postfix(source)
    print(contents)

4. Tips

1. Python에서 List를 Stack으로 사용하는 경우, 최 상위 element는 List의 맨 마지막 element에 해당하므로 따로 함수를 구현하지 않고, [-1]번째 element를 사용하는 것으로 대신할 수 있습니다. 아래 코드를 참고해 주십시오.

while stack[-1] != '(':

while len(stack) != 0:

5. 코드

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_03/Ch_03_11.py