[파이썬 자료구조] 스택(stack) - 파이썬을 이용한 중위 표기법 수식을 후위 표기법으로 변환하기

스택을 이용한 수식의 후위 표기법

• 중위 표기법

→ 연산자가 피연산자들 사이에 위치

(A+B)*(C+D)

 

 

• 후위 표기법

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

AB+CD+*

 

 

중위 표기 수식 → 후위 표기 수식 알고리즘

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):
    answer = ''
    opStack = ArrayStack()
    for i in range (len(S)):
        if S[i] in prec: 
            if S[i]=='(': # 열린 괄호는 그냥 스택에 집어 넣는다.
                pass
            else: # 그 외에 다른 연산자인 경우
                if opStack.isEmpty(): # 스택이 비어 있으면 연산자를 집어 넣는다.
                    pass
                while not opStack.isEmpty(): 
                # 스택이 비어 있지 않다면 스택에 있는 연산자와 S[i] 연산자 우선순위를 비교한다.
                    if prec.get(S[i]) > prec.get(opStack.peek()):
                        break 
                # S[i] 연산자 우선순위가 높다면 반복문을 빠져 나가 연산자를 스택에 집어넣는다.
                    answer+=opStack.pop() 
                # 그렇지 않다면 스택의 연산자를 내보내고 그다음 스택 연산자와 S[i] 연산자 비교
            opStack.push(S[i])
            i+=1
            continue
        elif S[i]==')': # 닫힌 괄호 일때는 열린 괄호가 나올때까지 pop
            while opStack.peek()!='(':  # 열린 괄호 나오기 직전까지 pop하여 answer에 적는다.
                answer+=opStack.pop() 
            opStack.pop() # 열린 괄호는 pop 해주고 answer에는 적지 않는다.
            i+=1
            continue
        else: # 문자 일때
            answer+=S[i] 
            i+=1
            continue
    while not opStack.isEmpty(): 
    # 입력된 수식을 한번 쭉 훑고 반복문이 끝난후 스택에 연산자가 남아 있는 경우
        answer+=opStack.pop() # 차례대로 pop하여 answer에 적어줌
    return answer

 

 

후위 표기 수식 계산 알고리즘

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 i in range (len(tokenList)):
        if tokenList[i] in prec: 
            if tokenList[i]=='(': 
                pass
            else: 
                if opStack.isEmpty(): 
                    pass
                while not opStack.isEmpty(): 
                    if prec.get(tokenList[i]) > prec.get(opStack.peek()):
                        break 
                    postfixList.append(opStack.pop()) 
            opStack.push(tokenList[i])
            i+=1
            continue
        elif tokenList[i]==')': 
            while opStack.peek()!='(': 
                postfixList.append(opStack.pop()) 
            opStack.pop() 
            i+=1
            continue
        else: 
            postfixList.append(tokenList[i]) 
            i+=1
            continue
    while not opStack.isEmpty(): 
        postfixList.append(opStack.pop()) 
    return postfixList


def postfixEval(tokenList):
    ops=ArrayStack()
    for i in range (len(tokenList)):
        if tokenList[i] in ['*','/','+','-']:
            a=ops.pop()
            b=ops.pop()
            if tokenList[i]=='*':
                result=b*a
            elif tokenList[i]=='/':
                result=b/a
            elif tokenList[i]=='+':
                result=b+a
            else:
                result=b-a
            ops.push(result)
            i+=1
        else:
            ops.push(tokenList[i])
            i+=1
    result=ops.pop()
    return result

            


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