계산기 프로그램 만들기 (파이썬, 후위 계산)

계산기는 숫자와 함께 다양한 연산자도 나타나고, 괄호도 처리해야 하며, 특히 연산자들의 우선순위도 고려해야 정확한 결과가 나온다. 기본적으로 수식은 연산자와 피연산자를 이용해 표현하는데, 이들의 상대적인 위치에 따라 다음과 세 가지 표기법으로 구분된다.

 

전위	중위	후위
연산자 피연산자1 피연산자1	피연산자1 연산자 피연산자2	피연산자1 피연산자2 연산자
+ A B	A + B	A B +
+ 5 * A B	5 + A * B	5 A B * +

 

컴퓨터는 다음과 같은 장점 때문에 후위표기 계산방법을 사용한다.

 

-  괄호를 사용하지 않아도 계산 순서를 알 수 있다.

- 연산자의 우선순위를 생각할 필요가 없다. 식 자체에 우선순위가 이미 포함되어 있기 때문이다.

- 수식을 읽으면서 바로 계산할 수 있다. 중위 표현식은 괄호와 연산자의 우선순위 때문에 수식을 끝까지 읽은 다음에야 계산이 가능하다.

 

계산기는 익숙한 중위표기(괄호 포함)로 수식을 입력할 수 있어야 하고, 컴퓨터가 이를 후위표기로 변환한 다음 그 식을 계산해야 한다. 즉, 중위표기의 후위표기 변환과, 후위표기 수식의 계산 과정이 필요하다. 이 과정은 스택을 이용한다.

 

 

- 스택을 이용한 후위표기 수식의 계산

 

8 2 / 3 - 3 2 * + 를 계산해 보자. 후위표기이므로 괄호는 수식에 포함되어 있지 않다.

 

1단계: ( 8 2 / ) 3 - 3 2 * +                       ->  4 3 - 3 2 * +

2단계: ( ( 8 2 / ) 3 - ) 3 2 * +                  ->  1 3 2 * +

3단계: ( ( 8 2 / ) 3 - ) ( 3 2 * ) +             ->  1 6 +

4단계: ( ( ( 8 2 / ) 3 - ) ( 3 2 * ) + )        ->  7

 

알고리즘을 정리해 보자. 수식을 왼쪽에서 오른쪽으로 스캔하다가 피연산자가 나오면 스택에 저장한다. 연산자가 나오면 스택에서 피연산자 두 개를 꺼내 연산을 실행하고 그 결과를 다시 스택에 저장한다. 이 과정은 수식이 모두 처리될 때 까지 반복되고, 마지막으로 스택에는 최종 계산 결과만 하나 남는다.

 

계산이 끝나면 스택에는 최종 계산 결과가 남아있다. 스택에는 하나의 항목만이 남아야 하고, 그 값을 꺼내 반환하면 된다.

 

 

구현

(연산자는 사칙연산 +, -, *, /로 제한한다.) 입력 수식은 리스트에 저장되어 있고, 연산자나 피연산자는 모두 리스트에 문자열로 저장된다고 가정한다. 즉 8 2 / 3 - 3 2 * +는 리스트에 다음과 같이 저장된다.

expr1 = [ '8', '2', '/', '3', '2', '*', '+' ]

스택을 하나 만들고, 각 리스트 항목들에 대해 그 항목이 피연산자이면 스택에 저장하면 된다. 저장되는 피연산자의 자료형은 실수형이 좋다. 정수를 계산하더라도 1/2와 같이 나눗셈을 하면 실수가 되기 때문이다.

항목이 연산자일 때 스택에서 피연산자들을 꺼내 계산한다. 스택에서 먼저 나오는 피연산자가 연산의 두번째 피연산자가 되어야 한다. 연산자로 계산한 결과는 다시 스택에 저장하면 되고, 이 과정을 입력 식의 끝까지 처리하면 계산이 끝난다.

 

<code>

class Stack:
    def __init__(self) -> None:
        self.top = []
        
    def isEmpty(self): return len(self.top) == 0
    def size(self): return len(self.top)
    def clear(self): self.top = []
    
    def push(self, item):
        return self.top.append(item)
    
    def pop(self):
        if not self.isEmpty():
            return self.top.pop(-1)
    
    def peek(self):
        if not self.isEmpty():
            return self.top[-1]


def evalPostfix(expr):
    s = Stack()    # 스택 객체 생성
    for token in expr:    # 리스트의 모든 항목에 대해
        if token in "+-*/":    # 항목이 연산자이면
            val2 = s.pop()     # 피연산자 2
            val1 = s.pop()     # 피연산자 1
            if token == '+': s.push(val1 + val2)    # 각 연산 수행
            elif token == '-': s.push(val1 - val2)  # 결과는 스택에
            elif token == '*': s.push(val1 * val2)  # 다시 저장
            elif token == '/': s.push(val1 / val2)
        else:    # 항목이 피연산자이면
            s.push(float(token))    # 실수로 변경하여 스택에 저장
    return s.pop()    # 최종 결과를 반환

 

 

 

- 스택을 이용한 중위표기 수식의 후위표기 변환

 

중위표기 수식에는 괄호가 포함되는데, 괄호를 이용해 어느 연산을 먼저 해야 할 지를 표시한다. 괄호가 없으면 연산자 우선순위에 따라 먼저 처리해야 할 수식을 결정해야 한다. 두 표기식의 공통점은 피연산자의 순서는 동일하다는 것이다. 연산자의 출력 순서는 연산자들의 우선순위 관계와 괄호에 의해 결정된다.

 

-  입력된 중위표기 수식을 순서대로 하나씩 스캔한다.

-  피연산자를 만나면 바로(후위표기 수식으로) 출력한다.

-  연산자를 만나면 어딘가에 잠시 저장해야 한다. 후위표기에서는 연산자가 피연산자들 뒤에 나오기 때문이다. 따라서 적절한 위치를 찾을 때까지 출력을 보류해야 한다. 연산자의 저장에는 스택이 사용된다.

 

예를 들어 a + b에서 a는 바로 출력되고 +는 저장되며 b도 출력되고, 최종적으로 저장되었던 +를 출력하면 후위표기식 a b +가 된다. a + b * c의 경우 a, b, c,는 그대로 출력되고 +와 *은 어딘가에 저장된다. 연산자 중에서 어떤 것이 먼저 출력되어야 하는지는 연산자 우선순위와 괄호를 고려해야 한다. 다음 세 가지 경우가 있다.

 

예제 1 ) 중위표기식 A + B * C의 후위 변환

1, 3, 5 단계는 피연산자이므로 바로 출력하면 된다. 연산자는 스택에 저장한다. 현재 연산자보다 우선순위가 높거나 같은 연산자는 먼저 출력한 후에 스택에 넣는다. ex) 스택에 +가 있을 경우 *이 들어올 수 있지만, *가 있을 경우 +가 들어오면 *을 먼저 출력한다.

 

 

예제 2 ) 중위표기식 A * B + C의 후위 변환

위의 수식은 *을 꺼내 출력하고 난 다음에 +를 스택에 삽입한다.

 

예제 3 ) 중위효기식 (A + B) * C의 후위 변환

-  왼쪽 괄호는 무조건 스택에 삽입한다. 왼쪽 괄호가 스택에 삽입되면 왼쪽 괄호를 제일 우선순위가 낮은 연산자로 취급한다. 즉 다음에 만나는 어떤 연산자도 스택에 바로 삽입된다.

 

- 오른쪽 괄호를 만나면 왼쪽 괄호가 삭제될 때까지 왼쪽 괄호위에 쌓여있는 모든 연산자들을 출력한다.

 

구현

먼저 연산자들의 우선순위를 정하는 함수를 구현해야 한다. 알고리즘에서 열리는 괄호는 우선순위가 가장 낮아야 하므로 0을 반환하고, 덧셈과 뺄셈은 1, 곱셈과 나눗셈은 2를 반환하도록 한다.

 

<code>

class Stack:
    def __init__(self) -> None:
        self.top = []
        
    def isEmpty(self): return len(self.top) == 0
    def size(self): return len(self.top)
    def clear(self): self.top = []
    
    def push(self, item):
        return self.top.append(item)
    
    def pop(self):
        if not self.isEmpty():
            return self.top.pop(-1)
    
    def peek(self):
        if not self.isEmpty():
            return self.top[-1]
        
        
def precedence(op):    # 연산자의 우선순위 반환
    if op == '(' or op == ')': return 0
    elif op == '+' or op == '-': return 1
    elif op == '*' or op == '/': return 2
    else: return -1
    

def Infix2Postfix(expr):    # expr: 입력 리스트(중위 표기식)
    s = Stack()
    output = []    # output: 출력 리스트(후위 표기식)
    for term in expr:
        if term in '(': s.push('(')
        elif term in ')':
            while not s.isEmpty():
                op = s.pop()
                if op =='(':
                    break 
                else:
                    output.append(op)
        elif term in '+-*/':
            while not s.isEmpty():
                op = s.peek()
                if precedence(term) <= precedence(op):
                    output.append(op)
                    s.pop()
                else:
                    break
            s.push(term)
        else:
            output.append(term)
            
    while not s.isEmpty():
        output.append(s.pop())
        
    return output