중위표기법을 후위표기법으로 바꾸고 이를 계산하는 알고리즘 2편

1. 후위표기식 계산

 

중위표기식을 알고리즘에 의해 후위표기식으로 바꾼 뒤에 이를 계산하는 방법은?

 

앞에서부터 차례로 읽어나가다가, 연산자를 만난다면, 바로 앞에 있는 두개의 피연산자를 해당 연산자로 계산하면 된다

 

특히 주의할 점이 -와 /인데, 먼저 꺼낸 피연산자가 오른쪽에 위치해야한다.

 

 

2. 알고리즘

 

후위표기식을 앞에서부터 차례로 읽어나간다.

 

2-1) 피연산자를 만나면 스택에 push

 

2-2) 연산자를 만나면 피연산자를 스택에서 차례로 pop하여 2개를 pop하면 연산을 수행하고, 결과를 다시 스택에 push한다.

 

2-3) 수식을 전부 읽으면 마지막에 남은 스택을 pop하여 출력

 

 

3. 예시를 통한 설명

 

 

피연산자 6,5,2,8을 읽어들이면 차례로 stack에 push합니다

 

 

피연산자 -를 읽으면, 스택에서 pop을 수행합니다.

 

여기서 -는 교환법칙이 성립하지 않으므로 주의해야합니다.

 

반드시 먼저 꺼낸 피연산자를 오른쪽에 위치시키고, 다음에 꺼낸 피연산자는 왼쪽에 위치시켜야합니다.

 

2 - 8 = -6으로 계산한 결과를 다시 스택에 push합니다.

 

 

다시 *을 만나면 스택에서 2개의 피연산자를 pop하고 계산하여 결과를 스택에 다시 push합니다.

 

 

2를 읽으면 스택에 push하고, /을 읽으면 스택에서 2개의 피연산자를 pop합니다.

 

먼저 꺼낸 피연산자가 오른쪽에 위치해야하며, -30/2=-15를 다시 스택에 push합니다.

 

 

마지막으로 +를 읽으면 스택에서 2개의 피연산자를 pop하고 계산을 하여 -9를 다시 stack에 push합니다.

 

더 이상 읽을 것이 없으면 마지막 남은 피연산자가 계산 결과이고, 이를 출력합니다.

 

 

4. 예시코드

 

postfix = input()

stack = []

#후위표기식을 앞에서부터 읽어들입니다.

for p in postfix:
    
    #후위표기식에 괄호는 존재하지 않으므로, stack이 처음에 비어있을수는 없습니다.
    
    if p >= '0' and p <= '9': #만약 읽은 단위가 피연산자이면
        
        stack.append(p) #스택에 push합니다.
    
    else: #만약 연산자를 읽어들이면..
        
        #stack에서 2번의 pop을 수행해 먼저 꺼낸 피연산자를 오른쪽에 위치시킵니다.
        
        #연산을 위해 int로 변환합니다.

        right = int(stack.pop())
        left = int(stack.pop())

        #연산한 결과를 다시 stack에 push합니다.
        #연산 결과를 str로 바꾸고 넣을 경우 에러날 수 있습니다.
        #예시) '-15.0'은 int로 바꾸면 에러남

        if p == '+':
            
            stack.append(left+right)
        
        elif p == '-':
            
            stack.append(left-right)
        
        elif p == '*':
            
            stack.append(left*right)
        
        else:
            
            stack.append(left/right)


print(stack[0]) #모든 후위표기식을 읽고나서 마지막에 남은 값이 계산결과입니다.

6528-*2/+
-9