중위표기식->후위표기식 변환(Stack)

(파이썬으로 작성)

 

 

전위표기식 --> 후위표기식 원리(스택 활용)

#1. 입력된 중위표기 수식을 순서대로 하나씩 스캔
#2. 피연산자를 만나면 바로 (후위표기 수식으로) 출력
#3. 연산자를 만나면 어딘가에 저장(스택사용)

 

from ArrayStack import Stack

#연산자의 우선순위 계산 함수
def precedence (op) :
    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(100)
    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

 

 

리스트를 활용해 문자열을 배열로 , 배열을 다시 문자열로

word = '((A+B)-C)+D*E' #수식
lis = [] #리스트 만들기

#반복을 활용해 연산자와 피연산자 모두 리스트로 옮기기
for i in word: 
    lis.append(i)
print(lis)

#출력값 문자열 -> 배열
#['(', '(', 'A', '+', 'B', ')', '-', 'C', ')', '+', 'D', '*', 'E']


postfix1 = Infix2Postfix(lis)

#join함수를 활용해서 다시 배열을 문자열(수식)으로 변환하기
tpostfix1 = ''.join(postfix1)
print(tpostfix1)

# 출력값 배열 -> 문자열(후위표기식 전환)
#AB+C-DE*+