괄호를 처리할 수 있는 사칙연산 계산기 (Python)

파이썬으로 간단한 사칙연산 계산기를 만들어보자. 실질적으로는 간단한 계산을 명령줄에서 수행할 수 있는 계산기가 필요해서 (계산기 앱을 실행하는게 귀찮…) 만들어보기로 했다.

실질적으로 간단한 덧셈, 나눗셈이 아니라, 다항식을 계산하고, 괄호가 들어있는 수식을 계산하는 기능이 필요했다. 따라서입력 자체는 명령줄 인자로 받으며, 가능한 한 ‘관대하게’ 처리하고자 했다.

이를 위해서는 입력받은 식을 공백이나 연산기호를 구분점으로 파싱하고, 후위식으로 변환한 후 이 후위식을 하나의 항으로 계산한 다음, 그 결과를 출력해주면 된다. 이들 각각의 과정을 함수로 만들고 최종적으로 하나의 코드로 조립해나간다.

입력된 식을 후위식으로 변환

중위식으로 표현된 식을 후위식으로 변환하는 과정은 이전 글에서도 명시했지만 다음과 같은 알고리듬을 따른다.

  1. 출력큐와 스택을 준비한다.
  2. 토큰이 숫자값이면 출력큐에 넣는다.
  3. 토큰이 왼쪽 괄호이면 스택에 넣는다.
  4. 토큰이 오른쪽 괄호이면 스택에서 왼쪽 괄호가 나올 때까지 스택에서 연산자를 꺼내어 출력큐에 넣어준다. 마지막으로 왼쪽 괄호를 꺼내어 버린다.
  5. 토큰이 그외의 연산자이면 스택에서 자신보다 우선순위가 같거나 큰 연산자를 꺼내어 출력큐에 넣은다음, 토큰을 스택에 넣는다.
  6. 2~5의 과정을 되풀이 하여 더 이상 토큰이 없으면 다시 스택으로부터 연산자를 꺼내어 출력큐에 넣는다.

이를 코드로 옮기면 아래와 같다. 연산자들을 별도로 정의하고, 각 연산자의 우선순위를 부여한다. 만약 거듭제곱 연산이나, 제곱근 연산이 필요한 경우에는 그에 맞는 연산자를 정의해서 추가해줄 수 있겠으나 여기서는 괄호와 사칙 연산만을 고려했다.

후위식 변환 함수 코드

입력된 수식은 토큰화 함수에 의해서 파싱되어 연산자/피연산자 단위의 토큰으로 분리한 후 처리한다. 따라서 실행 시점에 주의깊게 띄워쓰기를 지키지 않아도 입력된 식을 잘 처리할 수 있게 한다.

def parse_expr(expStr):
    tokens = tokenize(expStr)
    OP = ("*", "/", "+", "-", "(", ")")
    P = {
        "*" : 50,
        "/" : 50,
        "+" : 40,
        "-" : 40,
        "(" : 0
    }
    output = []
    stack = []

    for item in tokens:
        if item not in OP:
            output.append(item)
        elif item == "(":
            stack.append(item)
        elif item == ")":
            while stack != [] and 
                  stack[-1] != "(":
                output.append(stack.pop())
            stack.pop()
        else:
            while stack != [] and
                  P[stack[-1]] >= P[item]:
                output.append(stack.pop())
            stack.append(item)

    while stack:
        output.append(stack.pop())

    return output

후위식 계산 알고리듬

이렇게 만든 후위식은 다음과 같이 계산한다. 후위식의 계산은 사람이라면 뒤에서부터 추적해야 하지만, 컴퓨터는 역시 스택을 써서 계산한다. 기본적으로 후위식의 맨 뒤에서 토큰을 하나씩 꺼내는데, 연산자 피연산자1 피연산자2 순으로 꺼내어 계산한다. 이 때 만약 두 피 연산자 중 하나가 연산자가 나온다면, 다시 이어서 2개의 피연산자를 꺼내어 계산한 결과를 피연산자로 사용한다. 즉 뭔가 재귀 형태의 모양이 나오게 된다.

알고리듬으로 정리하면 다음과 같다. 여기서는 재귀꼴을 사용하지 않고 앞에서 처리하는 방식을 사용했다.

  1. 후위식 토큰을 앞에서 부터 읽는다.
  2. 토큰이 숫자값이면 스택에 푸시한다.
  3. 토큰이 연산자이면 스택에서 두 개의 값을 꺼내어 해당 연산자에 맞는 연산을 수행한다. 이 때 먼저 꺼낸 값이 연산자의 우변이 되어야 한다.
  4. 연산된 결과를 다시 스택에 푸시한다.
  5. 모든 토큰을 처리하면 스택에는 1개 값이 남는데, 이 값이 계산 결과이다.

이는 다음과 같이 코딩된다.

계산 함수 코드

def calc_expr(expStr):
    tokens = parse_expr(expStr)
    OP = ("*", "/", "+", "-",)
    FUNC = {
        "*": lambda x, y: y * x,
        "/": lambda x, y: y / x,
        "+": lambda x, y: y + x,
        "-": lambda x, y: y - x,
    }
    stack = []

    for item in tokens:
        if item not in OP:
            if '.' in item:
                stack.append(float(item))
            else:
                stack.append(int(item))
        else:
            x = stack.pop()
            y = stack.pop()
            stack.append(FUNC[item](x, y))

    return stack.pop()

토큰화 함수

수식을 후위식으로 변환하는 함수를 만들 때 보통 여러 고재들에서는 편의상 공백으로 분리되었다고 가정하는데, 실제로는 일일이 식을 띄워서 쓰는 것이 귀찮을때도 있고 경우에 따라서는 그렇지 않게 쓰여진 식을 그대로 계산해야 할 때도 있다. 따라서 숫자와 연산자를 구분하는 작업을 해야하는데, 파서를 써서 한자씩 읽어처리하는 방법도 있겠지만 너무 복잡하므로 간편하게 정규식을 사용한다.

import re
pat = r'(?:'          # 캡쳐하지 않는 그룹, 여기서는 조건문처럼 쓰인다.
      r'(?<=[^\d\.])' # look backward로 숫자나 점이 아닌 문자가 왼쪽에 있고
      r'(?=\d)'       # 오른쪽은 숫자가 있는 지점
      r'|(?=[^\d\.])'  # 만약, 숫자나 점 다음이라면, 그 다음은 숫자나 소수점이 아니어야 한다.
      r')'
regexp = re.compile(pat)

특이한 점은 이 정규식은 특정한 문자를 찾는 패턴이 아니라는 점이다. 이 정규식에서 찾는 패턴은 문자와 문자 사이의 틈이며, 왼쪽이 숫자나 소수점이 아니거나, 오른쪽이 소수나 숫자점이 아닌 곳을 찾는다고 보면 된다. 다음 그림은 이 정규식이 어디를 찾고 있는지를 시각적으로 보여준다.

어쨌든 이렇게 찾은 영역은 숫자값(피연산자)과 연산자간의 경계가 되므로 이 영역을 공백 문자로 치환하면 정성스럽게 공백으로 연산자나 괄호를 띄워서 쓴 것과 동일한 효과를 낼 수 있다.

result = re.sub(regexp, " ", expStr)

따라서 tokenize() 함수는 다음과 같이 코딩한다.

tokeninze 함수

def tokenize(expStr):
    RE = re.compile(r'(?:(?<=[^\d\.])(?=\d)|(?=[^\d\.]))', re.MULTILINE)
    return [x for x in re.sub(RE, " ", expStr).split(" ") if x]

이상을 조합하면 사칙연산 계산기가 완성된다. 이는 다음과 같이 수식 사이의 공백에 대해 신경쓰지 않아도 결과를 계산할 수 있게 한다.

C:>calc.py 1+ 2 * (45-3*(2 + 1))
73
  1. 프로그램이 실행되면 인자값의 개수를 센다. 인자가 없으면 무시하고 종료한다.
  2. 주어진 인자들은파싱함수에 전달되어 토근화되고 후위식으로 변환된다.
  3. 다시 이 값을 계산함수에 전달하여 수식을 계산한다.
  4. 결과를 출력한다.

아래는 전체 코드이다.