[Python 자료구조 #스택2] 스택을 이용한 중위표기 수식의 후위표기 변환

* 후위표기 수식 계산 구현

def evalPostfix(expr):
    s = Stack()
    for token in expr:
        if token in "+-*/":
            val2 = s.pop()
            val1 = s.pop()
            if (token == '+'):
                s.push(val1 + val2)
            elif (token == '-'):
                s.push(val1 - val2)
            elif (token == '*'):
                s.push(val1 * val2)
            elif (token == '/'):
                s.push(val1 / val2)
        else:
            s.push(float(token))

    return s.pop()

 

* 연산자(Operator) 우선순위 반환 함수

def precedence(op):	# op는 operator의 약자
    if op == '(' or op == ')':
        return 0
    elif op == '+' or op == '-':
        return 1
    elif op == '*' or op == '/':
        return 2
    else:
        return -1

 

* 중위표기식의 후위 변환 구현

def Infix2Postfix(expr):
    s = Stack()
    output = []
    for term in expr:
        if term in '(':
            s.push('(')
        elif term in ')':
            while not s.isEmpty():
                op = s.pop()
                if op == '(':
                    break
                else:
                    output.append(op)
        elif term in "+-*/":
            while not s.isEmpty():
                op = s.peek()
                if (precedence(term) <= precedence(op)):
                    output.append(op)
                    s.pop()
                else:
                    break
            s.push(term)
        else:
            output.append(term)

    while not s.isEmpty():
        output.append(s.pop())

    return output

 

* 테스트 

infix1 = ['8', '/', '2', '-', '3', '+', '(', '3', '*', '2', ')']
infix2 = ['1', '/', '2', '*', '4', '*', '(', '1', '/', '4', ')']
postfix1 = Infix2Postfix(infix1)
postfix2 = Infix2Postfix(infix2)
result1 = evalPostfix(postfix1)
result2 = evalPostfix(postfix2)
print('  중위표기: ', infix1)
print('  후위표기: ', postfix1)
print('  계산결과: ', result1, end='\n\n')
print('  중위표기: ', infix2)
print('  후위표기: ', postfix2)
print('  계산결과: ', result2)

--------------------------------------------------------------------------------------
  중위표기:  ['8', '/', '2', '-', '3', '+', '(', '3', '*', '2', ')']
  후위표기:  ['8', '2', '/', '3', '-', '3', '2', '*', '+']
  계산결과:  7.0

  중위표기:  ['1', '/', '2', '*', '4', '*', '(', '1', '/', '4', ')']
  후위표기:  ['1', '2', '/', '4', '*', '1', '4', '/', '*']
  계산결과:  0.5

 

출처 : 파이썬으로 쉽게 풀어쓴 자료구조