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

후위 표기 수식 계산

문제 설명

인자로 주어진 문자열 expr 은 소괄호와 사칙연산 기호, 그리고 정수들로만 이루어진 중위 표현 수식입니다. 함수 solution() 은 이 수식의 값을 계산하여 그 결과를 리턴하도록 작성되어 있습니다. 이 함수는 차례로 splitTokens(), infixToPostfix(), 그리고 postfixEval() 함수를 호출하여 이 수식의 값을 계산하는데,

• splitTokens() - 강의 내용에서와 같은 코드로 이미 구현되어 있습니다.
• infixToPostfix() - 지난 강의의 연습문제에서 작성했던 코드를 수정하여, 문자열이 아닌 리스트를 리턴하도록 작성합니다.
• postfixEval() - 이번 강의의 연습문제입니다. 함수의 내용을 완성하세요.

즉, 두 개의 함수 infixToPostfix() 와 postfixEval() 을 구현하는 연습입니다. 스택을 이용하기 위하여 class ArrayStack 이 정의되어 있으므로 그것을 활용하세요.

[참고] Python 에는 eval() 이라는 built-in 함수가 있어서, 이 함수에 문자열을 인자로 전달하면, 그 문자열을 그대로 Python 표현식으로 간주하고 계산한 결과를 리턴하도록 되어 있습니다. 이 built-in 함수 eval() 을 이용하면 이 연습문제는 전혀 직접 코드를 작성하지 않고도 정답을 낼 수 있을 것이지만, 스택을 이용하여 중위표현식을 계산하는 프로그래밍 연습을 위한 것이니, 강의 내용에서 설명한 절차를 수행하도록 코드를 작성해 보세요.

 

 

 

 

 

알고리즘 설계

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

 

 

 

 

코드 구현

class Stack:
    # 빈 스택을 배열로 초기화
    def __init__(self):
        self.data = [] 
        
    # 스택의 크기
    def size(self):
        return len(self.data)
    
    # 빈 스택 판단 여부
    def isEmpty(self):
        return self.size() == 0
    
    # 데이터 원소 추가
    def push(self, item):
        self.data.append(item)
        
    # 데이터 원소 삭제 (리턴)
    def pop(self):
        return self.data.pop()
    
    # 스택의 꼭대기 원소 반환
    def peek(self):
        return self.data[-1]


# 수가 문자열로 주어져 있을 때 (몇자리수인지 모르는상태) 
# 각각을 피연산자인 수와 연산자인 기호로 분리해서 리스트로 만드는 작업
# exprStr -> 중위 표현식으로된 수식
def splitTokens(exprStr):
    tokens = []
    val = 0                 # 각 자리 숫자를 담는 변수
    valProcessing = False   # 
    
    for c in exprStr:
        # 빈칸이 들어있으면 그냥 넘어감
        if c == ' ':
            continue
        
        # 숫자를 만나면 10진수로 변환하는 과정
        if c in '0123456789' :
            val = val * 10 + int(c)
            valProcessing = True # 수를 만났으므로 true
        
        # 숫자가 아니라면 (괄호 또는 연산자를 만났다고 간주) 10진수 표현이 끝난것
        else:
            if valProcessing:
                tokens.append(val)
                val = 0
            
            valProcessing = False # 지금 10진수를 처리하고있지 않다
            tokens.append(c)
        
    # 마지막 수 처리
    if valProcessing:
        tokens.append(val)
        
    return tokens



# 중위 표기법 -> 후위 표기법으로 바꾸는 함수
def infixToPostfix(tokenList):
    prec = {
        '*' : 3,
        '/' : 3,
        '+' : 2,
        '-' : 2,
        '(' : 1
    }
    
    opStack = Stack()
    postfixList = []
    
    for token in tokenList:
        # 피연산자이면 리스트에 추가
        if type(token) is int:
            postfixList.append(token)
            
        # '('이면 스택에 push
        elif token == '(':
            opStack.push(token)
            
        # ')' 이면 '('가 나올때까지 pop
        elif token == ')':
            while opStack.peek() != '(':
                postfixList.append(opStack.pop())
            opStack.pop()
        
        # 연산자이면 +-*/
        else:
            # 스택이 비어있을 경우 스택에 push
            if opStack.isEmpty():
                opStack.push(token)
                
            # 스택이 비어있지 않다면 비교
            else:
                
                # 스택에 값이 존재할 동안에 반복
                while opStack.size() > 0:
                    # 우선 순위가 스택안에 있는게 높으면 꺼낸다
                    if prec[opStack.peek()] >= prec[token]:
                        postfixList.append(opStack.pop())
                    else:
                        break
                
                opStack.push(token)
    
    # 반복문을 다 돌고 스택이 빌때까지 pop
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    
    # 리스트로 리턴한다
    return postfixList


# 후위 표기법을 계산하는 함수
def postfixEval(tokenList):
    valStack = Stack()
    
    for token in tokenList:
        # 피연산자를 만나면 스택에 push
        if type(token) is int:
            valStack.push(token)
            
        # 연산자를 만나면
        elif token == '+':
            n1 = valStack.pop()
            n2 = valStack.pop()
            valStack.push(n2+n1)
        
        elif token == '-':
            n1 = valStack.pop()
            n2 = valStack.pop()
            valStack.push(n2-n1)
            
        elif token == '*':
            n1 = valStack.pop()
            n2 = valStack.pop()
            valStack.push(n2*n1)
            
        elif token == '/':
            n1 = valStack.pop()
            n2 = valStack.pop()
            valStack.push(int(n2/n1))
        
    return valStack.pop()



def solution(expr):
    # 중위표현식을 tokens의 리스트 형태로 변환(피연산자, 연산자, 괄호)
    tokens = splitTokens(expr)
    # 리스트 형태로 저장된 토큰을 순서대로 후위표현식으로 변환
    postfix = infixToPostfix(tokens)
    # 후위표현식을 계산
    val = postfixEval(postfix)
    
    return val

expr = "10/2"
tokens = splitTokens(expr)
postfix = infixToPostfix(tokens)
val = postfixEval(postfix)

print(tokens)
print(postfix)
print(val)

 

룰루