프로그래머스 강의_13

스택의 응용

후위 표기 수식 계산

• 중위표기법 (연산자가 피연산자들의 사이에 위치)
• 후위표기법 (연산자가 피연산자들의 뒤에 위치)
• AB + CD+*
  앞 두개가 피연산자, 두 피연산자 사이에 적용할 연산자
• 연산자를 만났을 때 피연산자를 pop 해서 계산한 후 다시 스택에 push 한다.
• 다시 피연산자를 push하고 두개의 피연산자다음 연산자를 만났을 때 pop해서 계산한 후 다시 스택에 push한다.
• 뺄셈이나 나눗셈은 나중에 pop 한 피연산자가 연산의 앞쪽에 올 수 있도록 해야한다.
• 다음 곱셈을 만났을 때 push한 두 결과를 pop하여 연산한 후 다시 스택에 push한다.
• 후위표기식의 마지막에 도달하였을 때 스택에는 단 하나의 원소만이 남아있으며 pop해 값을 return 한다.

알고리즘의 설계

1. 후위 표현식을 왼쪽부터 한 글자씩 읽어서

• 피연산자이면 스택에 push
• 연산자를 만나면 스택에서 pop --> (1), 또 pop --> (2)
  ==> (2) 연산 (1) 을 계산, 이 결과를 스택에 push
• 수식의 끝에 도달하면
  연산이 올바르다면 마지막에 하나의 원소만 스택에 남아있고
  이 것을 스택에서 pop하면 결과를 알 수 있다.

연습문제

class ArrayStack:

    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이라는 문자열을 중위표현식으로 바꿔준다.
# 피연산자와 연산자를 분리해 tokens라는 리스트에 넣어준다.
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:
            if valProcessing:
                tokens.append(val)
                val = 0
            
            valProcessing = False 
            tokens.append(c)
        
    if valProcessing:
        tokens.append(val)
        
    return tokens
    
# 중위표기법을 후위표기법으로 바꿔 리스트에 담는다.
def infixToPostfix(tokenList):
    prec = {
        '*' : 3,
        '/' : 3,
        '+' : 2,
        '-' : 2,
        '(' : 1
    }
    
    opStack = ArrayStack()
    postfixList = []
    # 리스트를 처음부터 하나씩 꺼내 어떤 값이 있는지 반복한다.
    for token in tokenList:
        if type(token) is int:
            postfixList.append(token)
            
        # ( 을 만날 경우 스택에 push
        elif token == '(':
            opStack.push(token)
            
        # ) 을 만날 경우 수식이 끝났는지 확인하기위해 스택이 비어있지 않다면 pop 하고 스택이 비어있다면 push 한다.
        elif token == ')':
            while opStack.peek() != '(':
                postfixList.append(opStack.pop())
            opStack.pop()
        

        else:

            if opStack.isEmpty():
                opStack.push(token)
                
            # 연산자의 우선순위를 확인하기위해 딕셔너리의 value값을 비교하여 pop하거나 push한다.
            else:
                

                while opStack.size() > 0:
                    if prec[opStack.peek()] >= prec[token]:
                        postfixList.append(opStack.pop())
                    else:
                        break
                
                opStack.push(token)
    
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    
    return postfixList

# 후위 표기법을 리스트에서 꺼내 계산해 값을 리턴한다.
def postfixEval(tokenList):
    valStack = ArrayStack()
    
    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()