[Stacks]13. 후위 표기식 연산 구현 (Stack 응용)

목차

1. 중위 표기법, 후위 표기법

2. 후위 표기식 연산 방법

3. class Cal_post_fix

4. 테스트

 

1. 중위 표기법, 후위 표기법

1) 중위 표기법(Infix Notation)

- 연산자를 피연산자의 가운데 표기하는 방법을 말한다.

ex) A+B, A*B-C/D, A-B*C+D

 

2) 후위 표기법(Postfix Notation)

- 연산자를 피연산자 뒤에 표기하는 방법을 말한다.

ex) AB+, AB*CD/-, ABC*-D+

 

2. 후위 표기식 연산 방법

 후위 표기식을 입력받아 연산하는 방법은 다음의 과정과 같다.

1. 피연산자를 만나면 스택에 push한다.

2. 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고, 연산 결과를 다시 스택에 push한다.

3. 수식이 끝나면, 마지막으로 스택을 pop하여 출력한다.

 

3. class Cal_post_fix

class Cal_post_fix:
    def __init__(self, exp: str):
        self.stack = Stack_array() # 스택
        self.postfix = exp # 후위 표기식
        # self.size = len(self.postfix)
        
        for tmpch in self.postfix:
            if tmpch!='+' and tmpch!='-' and tmpch!='*' and tmpch!='/': # 피연산자 처리
                self.stack.push(int(tmpch))
            else: # 연산자 처리
                tmp2 = self.stack.pop()
                tmp1 = self.stack.pop()
                
                if tmpch=='+':
                    tmp2 = tmp1 + tmp2
                if tmpch=='-':
                    tmp2 = tmp1 - tmp2
                if tmpch=='*':
                    tmp2 = tmp1*tmp2
                if tmpch=='/':
                    tmp2 = tmp1/tmp2
                
                self.stack.push(tmp2)
        
        self.result = self.stack.pop()
    
    def res(self)-> int:
        return self.result

 

4. 테스트

if __name__ == "__main__":
    a = Cal_post_fix('23*63/-')
    print(a.res())
    
    b = Cal_post_fix('523*-7+')
    print(b.res())

 

예상 출력:

'''
4.0
6
'''

 

전체 코드는 github에 올려두었습니다.

github.com/imgzon3/algorithm/blob/main/Stack/cal_post_fix.py

imgzon3/algorithm