stack을 이용한 계산기 만들기

stack을 이용한 계산기 만들기입니다. 

반드시 이해해야 할 5개를 나열하고, 그다음 그림을 그려보면서 재차 이해해 봤습니다.

1. 스택은 LIFO다. 
따라서 최근 것이 먼저 나온다.

2. 계산기에서 스택은 연산 순서를 보류하는 용도다.

당장 계산 못 하면 쌓아둔다.

 

3. 연산자 우선순위가 핵심이다.

*,/ 가 +, - 보다 먼저이다.

 

4. 괄호는 우선 계산 범위를 강제로 지정한다.

' ( ' 만나면 특별 취급 해준다.

 

5. 후위표기식(Postfix Expression)은 계산이 엄청 쉽다.

숫자는 push, 연산자는 pop 2번 후 계산. 이때, push는 Python에는 없으므로 append로 입력

그림으로 이해해 보자.

Infix(중위 표기)

우선 infix에서는 2개의 list를 만든다 
하나는 출력될 OUTSTACK와, 하나는 연산자를 임시 저장할 OPSTACK이다.
그다음 Operand(피연산자)는 OUTSTACK에 append를 해준다. 
그다음 Operator(연산자)는 OPSTACK에 push를 해준다.
이때, ' ( ' 가 나오면 push 그 뒤에 ' ) ' 가 나오면 ' ( ' 가 나올 때까지 pop 해준다.

따라서, OUTSTACK에 담기는 순서는 OUTSTACK = ['4', '2', '6', '*', '+']이다.
OPSTACK에서 *이 마지막에 들어왔으니 스택은 LIFO 이므로, *이 먼저 그다음이 +이다.

 

자 이렇게 하면 그다음 Postfix 후위표기로 넘어간다.

Postfix(후위 표기)

우선, 4 2 6 * +라는 문자열을 받은 postfix는 계산을 해야 하므로 int를 이용해서 문자열을 숫자로 변환해야 한다.

OperandSTACK을 리스트로 만들어준 다음
해당 리스트 안에 피연산자를 push 해준다. 그리고 연산자는 2개의 값을 꺼내 pop를 해준다.
이때,

a = OperandSTACK.pop()
b = OperandSTACK.pop()을 해주게 되는데 

 먼저 pop 되는 값은 오른쪽 값이다. 따라서 a = pop() 먼저 하면 좌우가 뒤집혀서, 나중에 - , / 연산자가 나오면 값이 매우 달라질 수 있기 때문에 반드시
b = OperandSTACK.pop()  #오른쪽
a = OperandSTACK.pop()  #왼쪽
으로 해야 합니다.

 

그다음 
b = OperandSTACK.pop()
a = OperandSTACK.pop() 
OperandSTACK.push(a token b) 이때 token은 연산자를 의미합니다.  계산된 값을 push 해주어라 라는 의미입니다. 
그래서 2 * 6 = 12의 값을 인덱스 1에 넣어주고, 마지막으로 +를 4 + 12 해준다면 인덱스 0에 최종적으로 16이란 값이 남게 됩니다.

이것을 Python으로 구현해 보았습니다.

class Infix:
    def __init__(self):
        self.outstack = []   # 피연산자(결과) 저장
        self.opstack = []    # 연산자 임시 저장

    def precedence(self, op): #연산자 우선순위 함수 정의
        if op in '+-': # +- 와 */를 나눈 이유는 같은 연산자 그룹으로 취급하면, 계산 서순 문제 발생 ㅠ
            return 1 #우선도를 1 부여
        elif op in '*/':
            return 2 #우선도를 2 부여 우선도가 높기 때문에 계산 서순에 지장이 없음ㅋ
        return 0 # 그외에는 우선도 0 을 부여 

    def convert(self, expr): #expr은 Expression의 약자
        for token in expr:
            if token.isdigit():
                self.outstack.append(token)

            elif token == '(':
                self.opstack.append(token)

            elif token == ')':
                while self.opstack[-1] != '(':
                    self.outstack.append(self.opstack.pop())
                self.opstack.pop()

            elif token in '+-*/':
                while (self.opstack and
                       self.opstack[-1] != '(' and
                       self.precedence(self.opstack[-1]) >= self.precedence(token)):
                    self.outstack.append(self.opstack.pop())
                self.opstack.append(token)

        while self.opstack: #남은 연산자를 전부 꺼내서 outstack 뒤에 붙이는 과정 : opstack이 비어있지 않은 동안 계속 반복
            self.outstack.append(self.opstack.pop())

        return self.outstack # 최종 결과를 돌려줌 

class Postfix:
    def __init__(self):
        self.operandstack = [] # 연산값 저장

    def calculate(self, expr):
        for token in expr:
            if token.isdigit():
                self.operandstack.append(int(token)) #계산에는 문자열이 아닌 숫자가 필요하므로 int로 감싸자
            elif token in '+-*/':
                b = self.operandstack.pop()
                a = self.operandstack.pop()

                if token == '+':
                    self.operandstack.append(a + b)
                elif token == '-':
                    self.operandstack.append(a - b)
                elif token == '*':
                    self.operandstack.append(a * b)
                elif token == '/':
                    self.operandstack.append(a / b)
        
        return self.operandstack.pop()

#최종 계산기 테스트 
expr = "4+2*6"

infix = Infix()
postfix_expr = infix.convert(expr)
print("Postfix:", postfix_expr) # Postfix : postfix_expr 형식으로 출력해라

postfix = Postfix()
result = postfix.calculate(postfix_expr)
print("Result:", result) # Result : result 형식으로 출력

 

클래스를 Infix와 Postfix로 나누고
각각 내부 함수에 Infix에는 convert(변환)과  Postfix에는 calculate(계산) 함수를 넣어주었습니다.

Infix에서는 결국에는 필요한 게 숫자가 아닌 문자열만 Postfix에 보내버리면 되기 때문에 int를 사용할 필요가 없지만
Postfix에서는 계산을 해야 하기 때문에 int를 이용해서 token을 숫자로 변환시켜주어야 합니다.

***유튜브 : 신찬수 교수님의 자료구조 스택, 자료구조 스택 활용 - 계산기(1,2) 편이 많이 도움이 되었습니다.***
또한, 계산기를 만드는 과정에서 스택의 LIFO를 좀 더 깊게 이해할 수 있는 시간을 가졌습니다.