Algorithm

calculator

algorithm, caculator, python

  • 후위 표기법을 이용한 정수형 계산기 만들기

    • 3*5 처럼 연산자가 중간에 있는 경우를 중위 표기법이라고 한다.
    • *35 처럼 연산자가 앞에 있는 경우를 전위 표기법이라고 한다.

    • 35* 처럼 연산자가 뒤에 있는 경우를 후위 표기법이라고 한다.

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      후위 표기법

      - 컴퓨터가 계산하기 쉬운 수식
      - 괄호가 없다.
      - 연산자가 뒤에 위치

      [ 후위 표기법 적용 예 ]

      (3 + 2 * 2 - 4) * 3 + 2 * (5 - 7) = 322 * + 4 - 3 * 257 - * +
      5 * 7 - 5 / 3 + 2 + 5 * 3 = 57 * 53 / - 2 + 53 * +
      7 - 3 * 5 / 2 + (3 * 5 - 2 * 3) = 735 * 2 / - 35 * 23 * - +
      6 * (5 - 2 * 3) - (3 * 2 + 3 / 2 + 1) = 6523 * - * 32 * 32 / + 1 + -

  • 입력 시 피연산자는 1자리로 한다.

    • 연산자(Operator) : 연산을 수행하는 기호
    • 피연산자(Operand) : 연산에 참여하는 변수나 상수

  • 정수 연산이므로 ‘//‘ 사용

  • stack 사용

  • 후위 표기법으로 만드는 법

    • 최종 후위 수식을 담을 수식 리스트와 연산자를 가중치에 따라 담을 스택 리스트 필요

    • 각 연산자마다 가중치를 두어야 함

      • 1순위 : *, /
      • 2순위 : +, -
      • 3순위 : (, )

    • 수식 리스트에는 피연산자를 무조건 넣는다.

    • 연산자를 만나면 스택 리스트에 들어가는데 다음과 같은 규칙이 있다.

      • “(“는 스택 리스트에 연산자가 있건 없건 무조건 넣는다.
      • 연산자를 넣을 때, 가중치가 높으면 무조건 넣는다.
      • 가중치가 같으면 그 전에 쌓여있던 연산자를 빼서 수식 리스트에 넣는다.
      • 넣는 연산자 가중치가 작을 경우, 그 전에 쌓여있던 연산자를 빼서 수식 리스트에 넣는다.
      • 그 다음으로 넣을 때에도 가중치 비교를 계속해서 넣는다.
      • “)”를 만나면 “(“ 위에 쌓여 있는 모든 연산자를 수식 리스트에 넣는다.

  • 함수를 구현할 때 하나의 함수로 끝내는 것은 좋지 않다.

  • 기능을 가지고 있는 함수를 여러 개 만들어서 절차 지향적으로 실행하도록 한다.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    class Stack:

        def __init__(self):
            self.container = list()

        def empty(self):
            if not self.container:
                return True
            else:
                return False

        def push(self, data):
            self.container.append(data)
            
        def pop(self):
            return self.container.pop()
        
        def peek(self):
            return self.container[-1]


    def get_weight(opr):
        """
        get_weight(string) --> int
        연산자 비교를 위해 정수형 값을 반환
        """
        if opr == '*' or opr == '/':
            result = 2
            
        elif opr == '+' or opr == '-':
            result = 1
            
        elif opr == '(' or opr ==')':
            result = 0
            
        return result


    def conv_pfx(exp):
        """
        conv_pfx(string) --> string
        연산자와 피연산자를 후위표기법으로 변환
        """
        re_exp = exp.replace(' ', '')
        
        listExp = []
        
        oprStk = Stack()
        
        for i in range(len(re_exp)):
            if re_exp[i] == '*' or re_exp[i] == '/' or re_exp[i] == '+' or re_exp[i] == '-':
                if oprStk.empty():
                    oprStk.push(re_exp[i])
                else:
                    while get_weight(re_exp[i]) <= get_weight(oprStk.peek()):
                        listExp.append(oprStk.pop())

                        if oprStk.empty():
                            break

                    oprStk.push(re_exp[i])
                    
            elif re_exp[i] == '(':
                oprStk.push(re_exp[i])
                
            elif re_exp[i] == ')':
                while not oprStk.peek() == '(':
                    listExp.append(oprStk.pop())
                oprStk.pop()
            else:
                listExp.append(re_exp[i])

            if i == len(re_exp) - 1:
                while not oprStk.empty():
                    listExp.append(oprStk.pop())
                    
        return ''.join(listExp)


    def operator(f_num, l_num, opr):
        """
        operator(int, int, string) --> int
        연산자에 따라 연산을 수행하여 정수형 반환
        """
        if opr == '*':
            return f_num * l_num
        
        elif opr == '/':
            return f_num // l_num
        
        elif opr == '+':
            return f_num + l_num
        
        elif opr == '-':
            return f_num - l_num


    def calculator(exp):
        """
        calculator(string) --> int
        문자열 수식을 넣으면 결과값을 정수형으로 반환
        """
        pfx_exp = conv_pfx(exp)
        
        oprStk = Stack()
        
        for i in range(len(pfx_exp)):
            if pfx_exp[i] == '*' or pfx_exp[i] == '/' or pfx_exp[i] == '+' or pfx_exp[i] == '-':
                l_num = int(oprStk.pop())
                f_num = int(oprStk.pop())

                oprStk.push(str(operator(f_num, l_num, pfx_exp[i])))
            else:
                oprStk.push(pfx_exp[i])
                
            if i == len(pfx_exp) - 1:
                result = int(oprStk.pop())
                
        return result



    # 계산기 테스트

    exp1 = '(3 + 2 * 2 - 4) * 3 + 2 * (5 - 7)'
    print(conv_pfx(exp1))
    print(calculator(exp1))
    >> 322*+4-3*257-*+
       5

    exp2 = '5 * 7 - 5 / 3 + 2 + 5 * 3'
    print(conv_pfx(exp2))
    print(calculator(exp2))
    >> 57*53/-2+53*+
       51
Share