python - 스택 중위표기법을 후위표기법으로 구현

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 w in S :
        if w in prec :
            if opStack.isEmpty() :
                opStack.push(w)
            else :
                if w == '(' :
                    opStack.push(w)
                else :
                    while prec.get(w) <= prec.get(opStack.peek()) :
                        answer += opStack.pop()
                        if opStack.isEmpty() : break
                    opStack.push(w)
        elif w == ')' :
            while opStack.peek() != '(' :
                answer += opStack.pop()
            opStack.pop()
        else :
            answer += w
    
    while not opStack.isEmpty() :
        answer += opStack.pop()
    
    print(answer)
    
    return answer

 

중위표기법

: (A+B) * (C+D)

 

후위표기법

: AB+CD+*

 

 

 

 

변환 알고리즘 과정

 

1.

곱셈,나눗셈 계산순서를 3,

덧셈,뺄셈 계산순서를 2 로 정한 가정으로 시작

 

순차적으로 읽으면서 계산방법을 stack에 쌓는다.(push)

 > 계산방법 중, stack 끝에 있는 계산방법이(3) 읽은 계산방법(2)보다 크거나 같은 경우 먼저 pop하고 읽은 계산방법(2)를 stack에 쌓는다.

 

stack

-----

* (3)

-----

읽은 문자 : + (2)

 

* (3) >= + (2)   경우  -> * (3) pop 한다.

 

2.

괄호가 있는 경우, 어떤 계산순서보다 먼저 실행되며, 

읽은 문자가 '(' 경우 stack에 쌓고, 문자열에서 ')'을 읽는 순간 stack에서 '('을 찾을때까지 pop한다.

 

stack

-----

+

(

*

-----

 

읽은 문자 : ')'

꺼낼 문자 : +, (

 

 

3. 

문자열 다 읽으면, stack에 쌓여 있는 계산순서들을 pop한다.

 

-----

*

-----

 

꺼낼 문자 : *