사칙연산의 표현

이번 포스팅은 컴퓨터가 어떻게 사칙연산을 처리한는지에 대한 포스팅 입니다.

 

사칙연산 식을 표현할때는  3가지가 있다고 할 수 있습니다.

1.전위표기

2.중위표기

3.후위표기

전위, 중위, 후위 표기법 간의 관계

자 그러면 이제 이런 표기법이 왜 필요한지 의문이 드실겁니다.

 

우리가 Programming 언어로 Code를 짜고, 해당 Code를 기반으로 Computer가 동작합니다.

 

사람은 중위 표기법을 바로 이해할 수 있지만

 

컴퓨터가 중위표기법을 순서대로 해석할 경우 문제가 발생합니다.

 

컴퓨터와 사람의 중위표기법의 인지

사람의 경우 /와 *가 +, -보다 우선순위인걸 알기 때문에 식 전체를 보고, 우선순위부터 계산합니다.

 

하지만 컴퓨터가 중위표기법 그대로를 받는다면 순서대로 들어온 operand를 계산하기 때문에

 

실제 필요한 결과와는 다른 값이 나오는것을 확보실 수 있습니다.

 

이때, 만약 중위표기법의 식을 후위표기법으로 만든다면,

 

Stack을 활용해서 컴퓨터가 이해할 수 있는 사칙연산식을 표현하는것이 가능합니다.

 

Stack과 후위연산을 이용한 사칙연산의 표현

알고리즘은 간단하게

1. Operand가 아닌 문자가 들어오면 Stack에 추가한다(Push)

2. Operand가 들어오면 위에 두개의 문자를 꺼낸다(Pop x 2)

3. 두개의 문자를 대상으로 Operand를 적용한다(ex. BD/ => B/D)

4. Operand가 적용된 문자를 다시 Push한다

5. Stack이 empty가 될때까지 반복

이렇게 되면 컴퓨터는 순차적인 문자를 받아들이면서,

 

최종적으로는 사람이보는 중위표기법과 동일한 결과를 얻을수가 있습니다.

 

Programming 언어가 컴퓨터가 이해할 수 있는 기계어로 번역되는 과정에서 어쎔블리 언어로 변경되게 되는데,

 

이때 어쎔블리 언어에서 Stack을 지원하기 때문에 중위표기법을 후위표기법으로 바꾸고,

 

후위표기법이 최종적으로 기계어로 번역되어 계산이 이뤄진다고 할 수 있겠습니다 :)

 

Python으로 구현한 중위표기법의 전위, 후위표기법으로 변환하는 소스코드 입니다.

class ccal:
    def __init__(self, temp_string, order_type):
        self.formula = temp_string
        self.order_type = order_type
        self.count = self.counter()
        self.adj_formula = self.backorder()
        
        
    def counter(self):
        #입력된 formula의 "(",")" 수를 count합니다.
        #이때 개수를 count함과 동시에 "(",")" 의 text내 위치를 기록합니다
        Parenthesis_count = [0,[],0,[]]
        for i in range(len(self.formula)):
            if self.formula[i] == "(":
                Parenthesis_count[0] = Parenthesis_count[0] + 1
                Parenthesis_count[1] = Parenthesis_count[1] + [i]
            elif self.formula[i] == ")":
                Parenthesis_count[2] = Parenthesis_count[2] + 1
                Parenthesis_count[3] = Parenthesis_count[3] + [i]
        #만약 "(",")"의 개수가 동일하지 않다면 부정확한 formula이므로, Error를 발생시킵니다.
        if Parenthesis_count[0] != Parenthesis_count[2]:
            print("formula is not valid")
            raise ValueError
        else:
            return Parenthesis_count
    
    def backorder(self):        
        #operand를 다른 문자로 변경하기위한 Dict를 선언합니다.
        temp = {"*":"#","/":"$","+":"%","-":"^"}       
        #마지막에 coding된 문자를 원상복귀 시키기 위한 Dict를 선언합니다.
        temp_reverse = {"#":"*","$":"/","%":"+","^":"-"}          
        #text내에서 "("와 ")"의 위치를 가지고옵니다.
        left = self.count[1]
        right = self.count[3]        
        temp_formula = self.formula
        #모든 "(",")" Set을 정리할 때 까지 반복문을 진행합니다.
        while True:            
            #남아있는 ")"의 위치 중 가장 빠른 위치를 가지고옵니다.
            end = right.pop(0)
            for i in range(len(left)):
                #이때 남은 "("중 end에서 가장 가까운 위치를 찾습니다.
                #남은 "(" 중 선택해야하는 위치가 가장 마지막 "(" 위치인 경우 입니다.
                if i == len(left)-1:
                    start = left.pop(i)
                elif left[i+1]>end:
                    start = left.pop(i)
                    break            
            #text는 indexing 방식으로 수정이 안되기 때문에 temp 값에다가 문자를 추가합니다.
            temp_text = ""
            #start와 end사이의 text를 추출하여 operand인 경우 뒤로 넘겨서 후위표기를 만들어줍니다.
            #이때 operand를 그대로 뒤로 보낼경우 다른 () Set을 변경할 때 오류가 발생하므로
            #임시로 정한 coding 된 문자로 교체해줍니다.
            for i in range(end - start):
                if self.order_type == "back":
                    if temp_formula[end-i] in ["*","/","+","-"]:                    
                        temp_text = temp_text + temp[temp_formula[end-i]]
                    else:
                        temp_text = temp_formula[end-i] + temp_text
                elif self.order_type == "front":
                    if temp_formula[start+i] in ["*","/","+","-"]:                    
                        temp_text = temp[temp_formula[start+i]] + temp_text
                    else:
                        temp_text = temp_text + temp_formula[start+i]
            #이제 추출할 부분의 text를 기존 text에 수정해줍니다.
            temp_formula = temp_formula[:start] + temp_text + temp_formula[end:]
            #left와 right가 비어있다는것은 모든 ()set을 확인한 것이므로, 변경된 formula를 반환합니다.
            if len(left) == 0 or len(right)==0:
                final_text = ""
                for i in temp_formula:
                    #기존에 encoding한 operand를 decoding
                    if i in ["#","$","%","^"]:
                        final_text = final_text + temp_reverse[i]
                    #마지막에 "(",")"를 제거해줍니다.
                    elif i in ["(",")"]:
                        pass
                    else:
                        final_text = final_text + i
                return final_text
                
           
text = "(A-((B+K*F)/D))"
#text로 주어진 사칙연산을 전위표기법으로 변경
temp = ccal(text, "front")
print(temp.adj_formula)
=> "-A/*+BKFD"
#text로 주어진 사칙연산을 후위표기법으로 변경
temp = ccal(text, "back")
print(temp.adj_formula)
=> "ABKF*+D/-"