이번에는 후위 표현식으로 되어있는 수식을 계산하는 것을 스택을 활용하여 구현해보도록 하겠습니다!

스택의 응용 - 후위 표기 수식 계산

• 중위 표기법 (infix notation): 연산자가 피연산자들의 사이에 위치
  • (A + B) * (C + D)
• 후위 표기법 (postfix notation): 연산자가 피연산자들의 뒤에 위치
  • AB+CD+*
  • 괄호가 사라지고 연산자들은 순서대로 연산

• 피연산자를 만나면 스택에 push
• 연산자를 만나면 스택으로부터 2개의 피연산자를 뽑아내서 그 연산을 적용
• 중간에 만나는 연산을 행했을 때 그 연산 결과는 다시 스택에 넣어 다음 연산에 적용

예제
A B + C D + *

• [A, B] + > [A+B] > [A + B, C, D] + > [A+B, C+D] > [(A+B) (C+D)]

알고리즘의 설계

• 후위 표현식을 왼쪽부터 한 글자씩 읽어서
  • 피연산자이면 스택에 push
  • 연산자를 만나면 스택에서 pop -> (1), 또 pop -> (2)
    • (2) 연산자 (1)을 계산
    • 이 결과를 스택에 push
• 수식의 끝에 도달하면 스택에서 pop -> 이것이 계산의 결과

def splitTokens(exprStr):
수가 들어있는 수식을 수/기호로 변환하여 리스트로 출력

def splitTokens(exprStr):
	tokens = []
    val = 0
    valProcessing = False
    for c in exprStr:
    	if c == ' ':
        	continue
        if c in '0123456789':
        	val = val * 10 + int(c)
            valProcessing True
        else: 
        	# 수의 연산이 위에서 끝났으므로 tokens에 val을 입력
        	if valProcessing:
            	tokens.append(val)
                val = 0
            valProcessing = False
            tokens.append(c)
            
     # 마지막에 있던 게 수일 경우
     if valProcessing:
     	tokens.append(val)
        
     return tokens