[프로그래머스 알고리즘] 12강, 13강: 수식의 후위 표기법 및 수식 계산(Postfix Notation)

• 중위 표기법 (infix notation)

우리가 일반적으로 사용하는 표기법으로 연산자가 피연산자들의 사이에 위치

(A + B) * (C + D)

• 후위 표기법 (postfix notation)

연산자가 피연산자들 뒤에 위치

A B + C D + *

 

스택을 이용하여 중위 표현식을 후위표현식으로 바꾸기

중위 표현식	후위 표현식
A * B + C	A B * C +
A + B * C	A B C * +
A + B + C	A B + C +

 

괄호의 처리

• 여는 괄호는 스택에 push, 닫는 괄호를 만나면 여는 괄호가 나올 때까지 pop 
• 연산자를 만났을 때, 여는 괄호 너머까지 pop하지 않도록 여는 괄호의 우선순위는 가장 낮게 설정

중위 표현식	후위 표현식
(A + B) * C	A B + C *
A * (B + C)	A B C + *
(A + B) * (C + D)	A B + C D + *
(A + (B - C)) * D	A B C - + D *
A * (B - (C + D))	A B C D + - *

 

연산자의 우선순위 설정

prec = { '*' : 3, '/' : 3, '+' : 2, '-' : 2, '(' : 1 }

 

알고리즘 설계 - 후위 표현식 출력

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

• 피연산자면 그냥 출력
• '(' 이면 스택에 push
• ')' 이면 '('가 나올 때까지 스택에서 pop, 출력
• 연산자를 만나면 스택에서 이보다 높거나 같은 우선순위의 연산자를 pop, 출력한 뒤 연산자 스택에 push
• 스택에 남아있는 연산자는 모두 pop, 출력

 

알고리즘 설계 - 후위 표현식 계산

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

• 피연산자이면 스택에 push
• 연산자를 만나면 스택에서 pop하여 data1에 저장, 한 번 더 pop하여 data2에 저장, data2 연산 data1 계산해 스택에push
•  스식의 끝에 도달하면 스택에서 pop, 이 값이 계산 결과

 

 

 

 

 

12강 실습 : 중위표현 수식 --> 후위표현 수식

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]

prec = {
    '*': 3, '/': 3,
    '+': 2, '-': 2,
    '(': 1
}

def solution(S):
    opStack = ArrayStack()
    answer = ''
    for c in S:
        if (c not in prec) and (c != ')'):
            answer += c
        else:
            if c == ')':
                while str(opStack.peek()) != '(':
                    answer += str(opStack.pop())
                opStack.pop()
                
            elif c == '(':
                opStack.push(c)
            
            else:
                while (not opStack.isEmpty()) and (prec[c] <= prec[str(opStack.peek())]):
                    answer += str(opStack.pop())
                opStack.push(c)
                     
    while not opStack.isEmpty():
        answer += str(opStack.pop())
                
    return answer

13강 실습: 후위표현 수식 계산

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]


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 c in tokenList:
        if (c not in prec) and (c != ')'):
            postfixList.append(c)
        elif c == "(":
            opStack.push(c)
        elif c == ")":
            while str(opStack.peek()) != '(':
                postfixList.append(str(opStack.pop()))
            opStack.pop()
        else:
            while (not opStack.isEmpty()) and (prec[c] <= prec[str(opStack.peek())]):
                postfixList.append(str(opStack.pop()))
            opStack.push(c)
                    
    while not opStack.isEmpty():
        postfixList.append(str(opStack.pop()))  
     
    return postfixList

def postfixEval(tokenList):
    evalStack = ArrayStack()
    
    for c in tokenList:
        if isinstance(c, int):
            evalStack.push(c)
        else:
            data2 = evalStack.pop()
            data1 = evalStack.pop()
            if c == '+':
                val = data1 + data2
            elif c == '-':
                val = data1 - data2
            elif c == '*':
                val = data1 * data2
            else:
                val = data1 / data2
            evalStack.push(val)
        
    return evalStack.pop()



def solution(expr):
    tokens = splitTokens(expr)
    postfix = infixToPostfix(tokens)
    val = postfixEval(postfix)
    return val