[CS/Python] 자료구조 & 알고리즘 정리 - 연결 리스트, 스택, 후위 표기법

연결 리스트 (Linked lists)

연결 리스트는 선형 배열과는 유사한 구조이지만, 데이터 원소를 늘어놓는 방식에서 큰 차이가 있다. 선 형 배열이 "번호가 붙여진 칸에 원소들을 채워넣는" 방식이라고 한다면, 연결 리스트는 "각 원소들을 줄줄이 엮어서" 관리하는 방식이다.

 

연결 리스트가 가지는 이점은 원소의 삽입, 삭제가 선형 배열과 비교해 쉽게 처리할 수 있다는 것이다. 원소들이 link라는 고리로 연결되어 있기 때문에 가능한 일이다. 삽입/삭제가 빈번히 일어나는 응용에서 연결 리스트가 많이 이용되며, OS 내부에서도 많이 이용된다.

 

연결리스트가 가지는 단점도 물론 있다. 선형 배열에 비해 소요되는 메모리 요구량이 크다. 또한, 특정 위치의 원소를 찾기 어렵다. 선형 배열의 경우 index가 지정되어 있어 해당 원소를 바로 찾을 수 있는 반면, 연결 리스트는 앞에서부터 하나씩 연결된 링크를 따라가며 탐색해야 한다.

 

연결리스트의 장/단점

장점: 선형 배열에 비해 삽입/삭제가 쉽다.

단점: 메모리 요구량이 많다. 특정 위치의 원소를 찾는데 시간이 오래 걸린다.(선형 탐색과 유사)

 

단방향 연결 리스트 실습

1. 특정 원소 참조 (k번째 원소 찾기)

class Node:
    def __init__(self, item):
        self.data = item
        self.next = None

class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None

    def getAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None
        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1
        return curr

Node를 생성하는 클래스와 연결 리스트를 만드는 클래스가 위와 같다고 가정했을 때, 특정 원소를 찾는 방법은 위와 같다.

 

찾는 위치가 1 미만이거나 리스트의 전체 길이에 벗어났을 경우, None을 반환하고 해당 위치에 도달할 때까지 반복문을 실행한다.

 

2. 연결 리스트 순회

    def traverse(self):
        if self.nodeCount == 0:
            return []
        traverse_list = []
        curr = self.head
        while curr is not None:
            traverse_list.append(curr.data)
            curr = curr.next
        return traverse_list

연결리스트의 끝 지점까지 순회하며 데이터를 리스트에 넣는다. 물론 리스트가 존재하지 않을 경우(노드가 0개일 경우)는 빈 리스트로 반환한다.

 

self.head를 통해 curr를 첫 번째 로 지정해준 뒤 data를 리스트에 삽입한다. 그리고 .next를 통해 다음 노드로 이동하며 반복문을 수행한 뒤 결과 리스트를 반환한다.

 

3. 원소 삽입

    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False
        
        # 첫 번째 위치에 삽입할 시
        if pos == 1:
            newNode.next = self.head # 현재 첫번째 노드가 newNode의 next가 됨
            self.head = newNode

		# n번째 위치에 삽입 시
        else:
            if pos == self.nodeCount + 1: # 마지막 위치에 삽입 시
                prev = self.tail # 현재 마지막 노드를 prev로 지정
            else:
                prev = self.getAt(pos - 1) # pos번째 이전의 노드
            newNode.next = prev.next # newNode의 next를 prev의 next노드로 지정(맨 끝일 경우 None)
            prev.next = newNode # prev의 next노드를 newNode로 지정

        if pos == self.nodeCount + 1:
            self.tail = newNode

        self.nodeCount += 1 # nodeCount값 1 증가
        return True

연결 리스트 연산의 원소 삽입은 insertAt(self, pos, newNode)이라는 함수로 구성했다. pos가 가리키는 위치에 원소를 삽입하는 방식이다. pos는 물론 연결리스트의 범위 내여야 하므로, (1 <= pos <= nodeCount +1)의 값을 가져야 할 것이다.

 

위에서 봤던 getAt() 함수를 이용해 기본적으로 삽입이 가능하지만, 제일 첫 번째와 마지막에 들어갈 경우를 대비해 코드를 작성해야 한다.

 

4. 원소 삭제

    def popAt(self, pos): 
        if pos < 1 or pos > self.nodeCount: # pos가 범위를 벗어날 경우
            raise IndexError
            
        if pos == 1: # 첫 번째 원소를 삭제할 경우
            curr = self.head # 삭제할 값 저장
            self.head = self.head.next # self의 첫 번째 노드를 기존 첫 번째 노드의 next로 지정
            if self.nodeCount == 1: # 전체 리스트의 길이가 1일 경우
                self.tail = self.head # self.head가 None이 된 상태이므로 tail 또한 None
            
        else:
            prev = self.getAt(pos-1) # n-1번째 위치의 노드 찾기
            curr = prev.next # 삭제할 값(n번째 노드) 저장
            prev.next = curr.next # n-1번째 노드의 next를 삭제노드의 next로 지정
            if pos == self.nodeCount: # 마지막 위치일 경우
                self.tail = prev # n-1번째 노드를 tail로 지정
            
        self.nodeCount -= 1
        return curr.data

특정 위치의 node를 삭제하고 해당 값을 반환하는 코드이다. 우선 삭제하고자 하는 위치가 범위를 벗어날 경우 IndexError를 발생시키도록 했다.

 

첫 번째 원소를 삭제할 때 head노드를 2번째 노드로 지정해주는 것과 함께 전체 리스트의 길이가 1일 경우도 대비해 코드를 작성했다.

 

n번째 위치의 노드를 삭제할 경우에는 우선 삭제노드 이전의 노드를 찾은 뒤, 해당 노드의 next를 삭제 노드의 next로 연결된 노드로 이어주었다. 삭제 위치가 마지막일 경우를 대비해 이전 노드를 self.tail로 지정해주는 코드를 추가했다.

 

5. 두 리스트의 연결(concat)

    def concat(self, L):
        self.tail.next = L.head
        if L.tail:
            self.tail = L.tail
        self.nodeCount += L.nodeCount

self(현재 리스트)와 L(연결할 리스트)을 연결하는 연산이다. self의 마지막 노드인 self.tail의 마지막 노드의 다음 노드가 L의 첫번째노드(head)가 되도록 하면 된다. 그러나 L이 비어 있을 경우도 있으므로, L.tail이 존재할 때만 self.tail이 L.tail이 될 수 있도록 한다. 마지막으로 nodeCount값을 합쳐준다.

 

6. Dummy head를 이용해 연결 리스트 연산하기

class LinkedList:

	def __init__(self):
		self.nodeCount = 0
		self.head = Node(None) # 빈 노드(dummy node)
		self.tail = None
		self.head.next = self.tail

dummy node는 연결 리스트의 첫 번째에 추가되는 특별한 노드로, 실제 데이터는 가지고 있지 않으며 주로 연결 리스트의 구조를 단순화하고 코드의 예외 처리를 줄이기 위해 사용된다.

 

dummy node의 효과

• 헤드 처리 간소화: 연결 리스트 연산 시 head 노드를 처리할 때, 더미 노드가 있을 경우 예외처리를 하지 않아도 됨
• 코드 일관성 유지: 연결 리스트의 모든 노드에 대해 동일한 방식으로 접근할 수 있기 때문에, 추가 및 삭제 연산에서 코드가 더 일관적이고 간단해짐
• 빈 리스트 처리 용이: 더미 노드를 사용하면 리스트가 빈 경우에도 더미 노드 자체는 존재하기 때문에 빈 리스트를 특별히 처리할 필요가 없어짐
• 효율성 증가: 코드의 복잡도가 낮아짐

 

Dummy head를 가지는 연결 리스트의 특정 위치 원소 삽입

 

    def insertAfter(self, prev, newNode): # prev(이전 노드)와 newNode를 인자로 받음
       newNode.next = prev.next
       if prev.next is None: # 마지막 노드였을 경우 tail 조정
           self.tail = newNode
       prev.next = newNode
       self.nodeCount += 1
       return True


   def insertAt(self, pos, newNode):
       if pos < 1 or pos > self.nodeCount + 1:  #pos의 범위 확인 
           return False

       if pos != 1 and pos == self.nodeCount + 1:  #pos== nodeCount+1인 경우(마지막 위치에 삽입하는 경우)
           prev = self.tail
       else:  
           prev = self.getAt(pos - 1)
       return self.insertAfter(prev, newNode)

위 코드와 같이 제일 첫 번째 노드에 원소를 삽입할 시에 대한 예외처리를 따로 해주지 않아도 되기 때문에 코드가 간결해진다. insertAt() 함수에서 insertAfter() 함수를 호출하는 방식으로 해결할 수 있다.

 

Dummy head를 가지는 연결 리스트의 특정 위치 원소 삭제

	def popAfter(self, prev):
        if prev.next is None: # prev가 마지막 노드일 경우 None 반환 (pos == self.nodeCount인 경우)
            return None
        
        curr = prev.next
        if curr.next is None: # 리스트의 맨 끝을 삭제하는 경우 tail 조정
            self.tail = prev
        prev.next = curr.next
        self.nodeCount -= 1
        
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount: # 범위를 벗어날 경우 에러 발생
            raise IndexError
            
        prev = self.getAt(pos-1)
        return self.popAfter(prev) # popAfter메서드 사용시 self 붙여줄 것!

원소 삭제의 경우도 마찬가지로 첫 번째 노드(실제 값이 있는 부분)를 삭제할 때 예외 처리가 필요 없으므로 코드가 간소화된다.

 

 

양방향 연결 리스트 (Doubly Linked Lists)

위에서 배웠던 연결 리스트는 링크가 한 방향으로(앞에서 뒤로) 연결되어 있었다. 이번에 배우는 양방향 연결 리스트는 노드들이 앞/뒤로 연결되어 있다. 한 노드 별로 자신의 앞과 뒤로 연결된 링크를 2개씩 가지게 된다.

 

양방향 연결 리스트의 장/단점

• 장점: 데이터 원소를 탐색할 때, 앞 뒤로 움직일 수 있다. (작업의 유연성이 늘어남)
• 단점: 단방향 연결 리스트에 비해 메모리요구량이 늘어남, 삽입/삭제 연산 시 앞/뒤 링크 모두 조정해야 함

단방향 연결 리스트와 마찬가지로, 더미 노드 또한 앞 뒤로 둘 수 있다. 기대되는 효과 또한 동일하다.

 

# 노드의 구조 확장
class Node:

    def __init__(self, item): # 양방향으로 연결되는 노드 생성
        self.data = item
        self.prev = None
        self.next = None

# 리스트 구조 확장
class DoublyLinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None) # 더미 노드
        self.tail = Node(None) # 더미 노드
        self.head.prev = None # 맨 앞의 노드의 prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None # 맨 뒤 노드의 next = None

위 코드와 같이 노드와 리스트 구조를 구현하는 코드도 달라진 것을 확인할 수 있다. 노드는 생성 시 prev와 next 모두를 가지게 되고, 리스트 생성 시에는 더미 노드 2개가 서로 앞/뒤로 연결된 모습으로 생성된다.

 

리스트의 앞 뒤로 더미 노드를 두는데, 이 경우 더미 노드는 앞 또는 뒤로만 연결되어 있고 데이터가 있는 노드는 양 옆으로 연결되어 있는 구조를 가지게 된다. 즉, 데이터가 있는 노드들만의 공통점이 생긴다.

 

양방향 연결 리스트 순회

    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result
        
    # 역순회
    def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev
            curr = curr.prev
            result.append(curr.data)
        return result

단방향 연결 리스트와 큰 차이가 없지만, 유일하게 달라진 점은 while문의 조건이다. 이전에는 curr.next가 존재하는 경우에는 반복문이 지속 실행됐지만, 양방향 연결 리스트 구조에는 tail에도 더미 노드가 생성됐기 때문에 현재 노드의 다음(x2)의 노드가 존재할 때 반복문이 실행되도록 바뀌었다.

 

양방향 연결 리스트 원소 삽입

    def insertAfter(self, prev, newNode):
        next = prev.next
        # newNode의 링크 조정
        newNode.prev = prev
        newNode.next = next
        # prev와 next의 링크 조정
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)

단방향 연결 리스트에서 원소 삽입하는 것보다 조금 더 복잡해진 것 처럼 보인다. 다음 노드 뿐 아니라 이전 노드의 링크까지 연결시켜줘야 하기 때문이다.

 

하지만, 양 끝에 더미 노드가 존재하는 양방향 연결 리스트이기 때문에, 단방향 연결 리스트에서 tail을 조정시켜주는 예외 처리를 하지 않아도 된다. 오히려 코딩하기는 더 쉬워졌다.

 

양방향 연결 리스트 특정 원소 얻어내기

    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

	# 코드 추가
        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail # tail부터 시작(뒤부터 순회)
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

        return curr

양방향 연결 리스트 또한 앞에서 부터 순서대로 특정 원소를 찾는 방식이므로 일반적인 구현 방식은 달라진게 없다.

 

하지만, 이 경우 리스트 마지막에 원소를 삽입할 때 처음부터 끝까지 해당 위치를 찾은 다음에 원소를 삽입(삭제) 해야 하므로 시간이 매우 오래 걸린다.

 

이 문제를 해결하기 위해서 pos 인자가 (nodeCount // 2)값 보다 클 경우, 앞에서부터 순회하는 것이 아닌 뒤에서 부터 역순회하도록 했다.(위 reverse 메서드 참고)

 

특정 원소 '앞'에 원소 삽입하기

    def insertBefore(self, next, newNode): # 인자로 next를 받음
        prev = next.prev # next node의 prev를 먼저 구함
        newNode.next = next
        newNode.prev = prev
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True

위 getAt() 메서드에서 활용한 역순회를 원소 삽입에도 적용하기 위해 insertBefore()라는 메서드를 만들 수 있다. 뒤에서부터 순회하기 때문에, 삽입할 위치 다음 노드가 인자로 들어가게 된다.

 

특정 원소 앞/뒤에 원소 삭제하기

    def popAfter(self, prev):
        curr = prev.next
        next = prev.next.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data


    def popBefore(self, next):
        curr = next.prev
        prev = next.prev.prev
        next.prev = prev
        prev.next = next
        self.nodeCount -= 1
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
            
        # popBefore() 메서드 사용하는 경우
        next = self.getAt(pos).next # pos가 중간 위치 이상일 경우에만 역순회하므로
        return self.popBefore(next)
        
        # popAfter() 메서드 사용하는 경우
        prev = self.getAt(pos - 1)
        return self.popAfter(prev)

원소 삽입과 크게 다르지 않다. getAt() 메서드가 pos값에 따라 순회하는 방향이 다르므로, popBefore() 메서드를 활용할 경우에는 next 인자값에 유의하자.

 

양방향 연결 리스트의 병합

    def concat(self, L):
        if self.nodeCount == 0: # self 리스트가 빈 리스트일 경우
            self.head.next = L.head.next
            L.head.next.prev = self.head
            self.tail = L.tail
        elif L.nodeCount == 0: # L(병합하고자 하는 리스트)이 빈 리스트 일 경우
            pass # 병합 필요없음
        else:
            self.tail.prev.next = L.head.next # 양 끝에 있는 더미노드 고려
            L.head.next.prev = self.tail.prev
            self.tail = L.tail
            
        self.nodeCount += L.nodeCount
        return True

 

 

스택(Stack)

추가된 데이터 원소들을 끄집어내면 마지막에 넣었던 것부터 넣은 순서의 역순으로 꺼내지는 자료 구조를 스택 (stack) 이라고한다. 후입선출(LIFO - Last-in First-out)의 특징을 가진다.

 

스택에 데이터를 추가하는 행위를 push연산이라고 하고, 마지막으로 추가된 데이터를 참조하고 삭제하는 동작을 pop연산이라고 한다. 컴퓨터 내부에서 마지막으로 호출된 곳으로 돌아가는 동작을 구현하는 것을 예시로 생각하면 된다.

 

스택을 위에서 배운 연결리스트로 구현하게 되면 아래 코드와 같다.

class LinkedListStack:

	def __init__(self):
		self.data = DoublyLinkedList()

	def size(self): # 현재 스택의 원소 수를 구함
		return self.data.getLength()

	def isEmpty(self): # 스택이 비어있는지 판단
		return self.size() == 0

	def push(self, item): # item 데이터를 스택에 추가
		node = Node(item)
		self.data.insertAt(self.size() + 1, node)

	def pop(self): # 가장 나중에 저장된 데이터 원소를 제거 후 데이터 반환
		return self.data.popAt(self.size())

	def peek(self): # 가장 나중에 저장된 데이터 원소를 반환 (제거하지 않음)
		return self.data.getAt(self.size()).data

 

스택 오버플로우와 언더플로우

• 스택 오버플로우 - 꽉 차 있는 스택에 데이터 원소를 push할 경우 발생하는 에러
• 스택 언더플로우 - 비어있는 스택에 데이터 원소를 pop할 경우 발생하는 에러

파이썬 라이브러리 사용해 stack 구현

from pythonds.basic.stack import Stack

S = Stack()
dir(S) # pythonds 라이브러리로 구현된 Stack의 메서드 확인

>>>
['__class__',
 '__delattr__',
 '__dict__',
 '__dir__',
 '__doc__',
 '__eq__',
 '__format__',
 '__ge__',
 '__getattribute__',
 '__gt__',
 '__hash__',
 '__init__',
 '__init_subclass__',
 '__le__',
 '__lt__',
 '__module__',
 '__ne__',
 '__new__',
 '__reduce__',
 '__reduce_ex__',
 '__repr__',
 '__setattr__',
 '__sizeof__',
 '__str__',
 '__subclasshook__',
 '__weakref__',
 'isEmpty',
 'items',
 'peek',
 'pop',
 'push',
 'size']

pythonds 라이브러리를 통해 stack을 이용할 수도 있다.

 

수식의 후위 표기법 (스택 응용)

우리가 일상에서 사용하는 수식의 표기법은, 중위 표기법 (infix notation) 이라고 부를 수 있다. 두 개의 피연산자 A 와 B 를 가지고 덧셈을 하는 수식을 표기하면 A + B 와 같이 되는데, 이 때 연산자인 + 가 두 피연산자의 사이에 (가운데에) 위치하기 때문에 중위 표기법이라고 부른다. 그렇다면 후위 표기법이란 무엇일까? 연산자를 두 피연산자의 뒤에 쓰는 방식이다. 따라서 앞의 예인 A + B 를 후위 표기법으로 표기하면 AB+ 가 된다.

 

ex) (A + B) * (C + D)
후위 표기법으로 변환시
A B + C D + *

ex) A + B * C
A B C * +

 

스택을 이용해 중위 표기법을 후위 표기법으로 변환할 수 있다. 왼쪽부터 순회하며 피연산자는 그대로 두고, 연산자만을 비교해 스택을 쌓는다. 스택 내 연산자와 새로운 연산자를 비교했을 때 스택 내 연산자가 우선순위가 높다면 pop하여 식에 추가되고, 아니라면 그대로 스택에 새로운 연산자가 추가된다.

 

ex) A * B + C

1. A는 피연산자 이므로 그대로 둠 (A)

2. *은 연산자이며, 스택은 현재 비어있으므로 스택에 push (A)

3. B는 피연산자 이므로 그대로 둠 (A B)

4. +는 연산자이며, 스택에 마지막으로 추가된 연산자와 우선순위를 비교

5. *가 +보다 우선 순위가 높으므로 pop하여 수식에 추가되고, +는 스택에 추가 (A B *)

6. C는 피연산자이므로 그대로 배치 (A B * C)

7. 전부 순회 완료. 스택에 남아 있는 연산자 뒤에 배치 (A B * C +)

 

괄호의 처리

ex) (A+B) * C

여는 괄호는 스택에 push, 닫는 괄호를 만나면 여는 괄호가 나올 때까지 pop한다. 여는 괄호 너머까지 pop하는 것을 방지하기 위해 여는 괄호의 우선순위는 가장 낮게 설정되어야 한다.

 

알고리즘의 설계

먼저 연산자에 대한 dictionary를 준비한다.

prec = {
	'*':3, '/':3,
        '+':2, '-',2,
        '(':1
        }

그리고 중위 표현식을 왼쪽부터 차례대로 읽는다. 이 때,

 

1. 피연산자이면 그냥 출력

2. '('일때 스택에 push

3. ')'이 나오면 '('이 나올 때까지 스택에서 pop하여 출력

4. 연산자라면 스택에서 이보다 높거나 같은 우선순위의 연산자를 pop하여 출력한다. (그리고 해당 연산자는 스택에 push)

5. 중위 표현식을 모두 읽었다면 스택에 남아있는 연산자 모두 pop하여 출력

 

후위 표기법 변환 알고리즘 구현

def solution(S):
    opStack = ArrayStack()
    answer = ''
    for i in list(S): # S는 문자열이므로 list형태로 변환
        if i.isalnum(): # i가 문자형일 경우 그대로 추가
            answer += i
        elif i == '(': # 여는 괄호일 경우 바로 push
            opStack.push(i)
        elif i == ')': # 닫는 괄호가 나왔을때
            top_token = opStack.pop() # 빈 스택에서 pop하지 않도록 변수 지정
            while top_token != '(': # 여는 괄호가 나올 때까지 반복
                answer += top_token
                top_token = opStack.pop()
        else:
            while opStack.size() >= 1 and prec[opStack.peek()] >= prec[i]: # 우선 순위 고려
                answer += opStack.pop()
            opStack.push(i)
            
    while opStack.size() >= 1: # 반복문이 종료된 경우 스택에 있는 연산자 모두 꺼냄
        answer += opStack.pop()
                
    return answer

 

 

후위 표기법 계산 알고리즘

후위 표기법은 연산자가 피연산자들의 뒤에 위치하는 특징을 가지고 있다. 이를 이용하면 후위 표기식 계산을 위한 알고리즘을 만들 수 있다. 중위 표기법을 후위 표기법으로 변환할 때와 반대로, 이번에는 피연산자가 스택에 쌓이고 연산자를 만날 때마다 2개의 피 연산자를 스택에서 pop하여 계산하는 방식으로 문제를 풀이할 수 있다.

 

ex) A B + C D + *

1. 스택에 A push

2. 스택에 B push

3. 연산자 +를 만나 스택에 쌓여있는 피연산자 B와 A를 순서대로 pop하여 더한 뒤 스택에 다시 push

4. 스택에 C push

5. 스택에 D push

6. 연산자 +를 만나 D와 C를 더한 뒤 스택에 다시 push

7. 연산자 *를 만나 A+B와 C+D를 곱해준다.

 

* 빼기 연산자와 나누기 연산자의 경우 스택에서 2번째로 나온 피연산자가 앞에 가도록 수식을 구성해야 함

 

def postfixEval(tokenList):
    opStack = ArrayStack() # 스택 생성
    
    for t in tokenList: # tokenList는 숫자와 연산자로 이루어진 리스트
        if isinstance(t, int): # t가 int형일 경우 stack에 push
            opStack.push(t)
        elif t == '+':
            a = opStack.pop()
            b = opStack.pop()
            opStack.push(a+b)
        elif t == '-': # 빼기 연산자의 경우 순서 유의
            a = opStack.pop()
            b = opStack.pop()
            opStack.push(b-a)
        elif t == '*':
            a = opStack.pop()
            b = opStack.pop()
            opStack.push(a*b)
        else: # 나누기 연산자의 경우 순서 유의
            a = opStack.pop()
            b = opStack.pop()
            opStack.push(b/a)
            
    val = opStack.pop() # 최종 결과
    return val