스택의 응용 - 수식의 후위 표기법 (Postfix Notation)

중위 표기법 ( infix notation )

• 연산자가 피연산자들의 사이에 위치
• ( A + B ) * ( C + D )

후위 표기법 ( postfix notation )

• 연산자가 피연산자들의 뒤에 위치
• A B + C D + *

 

 

 

중위 표현식 -> 후위 표현식

스택에 있는 수식의 우선순위가 크거나 같을 때 먼저 꺼낸다

A + B * C

 

 

 

괄호의 처리

여는 괄호는 스택에 push, 닫는 괄호를 만나면 여는 괄호가 나올 때 까지 pop한다.

연산자를 만났을 때, 여는 괄호 너머까지 pop하지 않도록 하려면 여는 괄호의 우선순위는 가장 낮게 설정해야한다.

 

 

 

알고리즘 설계

연산자의 우선순위 설정은 파이썬 사전을 활용하여  prec를 생성한다.

중위 표현식을 왼쪽부터 한 글자씩 읽어서 피연산자이면 그냥 출력, '('이면 스택에 push, ')'이면 '('이 나올 때까지 pop해서 출력한다. 연산자를 만나면 스택에서 이보다 높거나 같은 우선 순위인 것들을 pop해서 출력한다. 우선 순위가 같은것은 왼쪽에 있는 연산자를 pop, 그리고 이 연산자를 스택에 push해둔다.

스택에 남아있는 연산자는 모두 pop해서 출력한다.

 

스택의 맨 위에 있는 연산자와의 우선순위 비교해서 우선순위가 같거나 높은 연산자를 pop해서 출력하도록한다. 비교하기 위해서 스택의 peek() 연산을 이용한다.

스택에 남아있는 연산자 모두 pop()하는 순환문은 while not opStack.isEmpty(): 를 이용한다.

 

 

 

 

문제 설명

중위 표기법을 따르는 수식 S 가 인자로 주어질 때, 이 수식을 후위 표기법을 따르는 수식으로 변환하여 반환하는 함수 solution() 을 완성하세요.

인자로 주어지는 수식 문자열 S 는 영문 대문자 알파벳 한 글자로 이루어지는 변수 A - Z 까지와 4칙연산을 나타내는 연산자 기호 +, -, *, /, 그리고 여는 괄호와 닫는 괄호 (, ) 로 이루어져 있으며 공백 문자는 포함하지 않는 것으로 가정합니다. 또한, 올바르게 구성되지 않은 수식은 인자로 주어지지 않는다고 가정합니다. (수식의 유효성은 검증할 필요가 없습니다.)

문제에서 미리 주어진, 연산자의 우선순위를 표현한 python dict 인 prec 을 활용할 수 있습니다.

또한, 스택의 기초 강의에서 이미 구현한, 배열을 이용한 스택의 추상적 자료 구조 코드가 이미 포함되어 있으므로 그대로 이용할 수 있습니다.

 

 

 

내가 푼 코드

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 = ''
    flag = False # (를 확인하기위해
    
    for char in S:
        # 피연산자인 경우 그냥 출력
        if char in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
            answer += char
        
        # 피연산자가 아닌 경우 +-*/() 인 경우
        else:
            if char == '(':
                flag = True
            elif char == ')':
                flag = False
            
            # 빈 스택인 경우에 push
            if opStack.isEmpty() or flag == True:
                if char != '(':
                    opStack.push(char)
            
            # 빈 스택이 아니면 peek과 비교
            else:
                if char == ')':
                    answer += opStack.pop()
                else:
                    peek = opStack.peek()
                    if prec[peek] >= prec[char]:
                        answer += opStack.pop()
                        opStack.push(char)
                    else:
                        opStack.push(char)
            
            
    while not opStack.isEmpty():
        answer += opStack.pop()

    return answer

 

 

테스트 7과 8에서 실패,,

 

두번째로 푼 코드

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 char in S:
        
        # 피연산자이면 그냥 출력
        if char in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
            answer += char
        
        # '('이면 스택에 push
        elif char == '(':
            opStack.push(char)
        
        # ')' 이면 '(' 이 나올 때까지 pop, 출력
        elif char == ')':
            while opStack.peek() != '(':
                answer += opStack.pop()
            opStack.pop()
        
        # 연산자일 경우
        else:
            # 빈 스택인 경우에 push
            if opStack.isEmpty():
                opStack.push(char)
            else:
            
            	### 문제가 되는 부분 ###
                peek = opStack.peek()

                if prec[peek] >= prec[char]:
                    answer += opStack.pop()
                    opStack.push(char)
                else:
                    opStack.push(char)
                #########################
                    
    while not opStack.isEmpty():
        answer += opStack.pop() 
                
    return answer

자꾸 어렵게 생각한 것 같다. 괄호를 어떻게 처리해야하나 자꾸 answer에 같이 들어가서 왜그런걸까 오늘 하루종일 짱구를 굴려봤지만 그냥 강의에서 말하는대로 하면되는것을 왜 어렵게 생각한걸까ㅠㅠ 여튼 여기까지했을 때 테스트 7,8에서 오류가 난다. 질문하기를 살펴봤는데

A + B * C - D 이 경우에서 C가 들어가고 그 다음 -를 만났을 때 *는 처리가 되지만 먼저 들어가있던 +도 꺼내서 처리해야하는게 문제였다ㅠㅠ 머리아파 죽겄네

 

연산자를 만나면 취해야하는 행동

- 현재 스택에 들어있는 원소들을 검사하면서 (후입선출 순서로) 지금 마주친 연산보다 우선순위가 높거나 같은 연산자들을 pop하여 answer에 덧붙인다.

- 그 후 스택이 비거나 우선순위가 낮은 놈이 위치한 경우 char를 push

 

 

 

 

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 char in S:
        
        # '('이면 스택에 push
        if char == '(':
            opStack.push(char)
            
        # ')'이면 '('가 나올 때까지 pop, 출력
        elif char == ')':
            while opStack.peek() != '(':
                answer += opStack.pop()
            opStack.pop()
            
        # 연산자가 나올 경우
        elif char in '+-*/':
            # 스택이 비어있으면 push
            if opStack.isEmpty():
                opStack.push(char)
            # 비어있지 않다면 비교
            else:
                # 헤맸던 부분ㅜㅜ해결
                while opStack.size() > 0 :
                    # 우선 순위 비교 후 밖에 있는 놈이 낮으면 꺼내고 계속 비교
                    if prec[opStack.peek()] >= prec[char]:
                        answer += opStack.pop()
                    # 우선 순위가 밖에 있는 놈이 높으면 반복문 탈출
                    else:
                        break
                opStack.push(char)
                
        # 피연산자인 경우
        else:
            answer += char

    # 스택이 빌 때 까지 pop
    while not opStack.isEmpty():
        answer += opStack.pop() 
                
    return answer

새로운 마음으로 다시 풀어봤다. 해결했다. 간단하네 흥