(Python/Stack) 중위표현 수식 > 후위표현수식

문제 출처: 프로그래머스 어서와! 자료구조와 알고리즘은 처음이지?

 

문제 풀이:

 

# 문제에 주어진것

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 solution1(S):
    answer = ''
    opstact = ArrayStack()

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

 

 

def solution1(S):
    answer = ''
    opstact = ArrayStack()

    prec = {
        '*': 3, '/': 3,
        '+': 2, '-': 2,
        '(': 1
    }
    for i in S:
        if i == '(':
            opstact.push(i)
        elif i == ')':
            while opstact.peek() != '(':
                answer += opstact.pop()
            opstact.pop()
        elif i in prec :
            if opstact.isEmpty():
                opstact.push(i)
            else:
                while opstact.size() > 0:
                    if prec[opstact.peek()] >= prec[i]:
                        answer += opstact.pop()
                    else:
                        break
                opstact.push(i)
        else:
            answer += i
    while not opstact.isEmpty():
        answer += opstact.pop()
    return answer

 

'(' 를 만나면 스택에 넣고 그 위에 ')' 나오기 전까지 피연산자를 answer 에 담고 ')' 나오면 스택에 있던거를 다 뽑는다.

 

스택이 비어 있다면 다시 넣고 스택에 연산기호가 있다면 

 

벨류값을 비교해 스택에 있는 벨류가 큰 값은 다 뽑아준다.