[자료구조] 스택 - 중위표현식 후위표현식으로 변환

728x90

 

 

 

🙆‍♂️ 후위표현식으로 변환하기

---

"""
스택 클래스 Stack
def emt : 스택에 값이 없다면 True를 반환 있다면 False를 반환
def size : 스택의 현재 길이를 반환
def clear : 스택 값을 초기화
def push : 입력 요소 ch를 스택에 입력
def pop : 스택의 최상단 값을 삭제
def peek : 스택의 최상단 값 반환
def disply : 스택의 상태를 출력
"""
class Stack:
    def __init__(self):
        self.stack=[]
    def emt(self):
        return len(self.stack)==0
    def size(self):
        return len(self.stack)
    def clear(self):
        self.stack=[]
    def push(self,ch):
        self.stack.append(ch)
    def pop(self):
        if not self.emt():
            return self.stack.pop(-1)
    def peek(self):
        if not self.emt():
            return self.stack[-1]
    def display(self):
        print(self.stack)

위의 만들어둔 스택 클래스를 이용했습니다.

 

 

"""
후위 변환
"""
import re

def check(op):
    if op in ['(',')']:
        return 0
    elif op in ['+','-']:
        return 1
    elif op in ['*','/','%']:
        return 2
    else:
        return -1

def inToPost(string):
    st = Stack()
    output=[]
    for i in string:
        if i == '(':
            st.push('(')
        elif i == ')':
            while not st.emt():
                op = st.pop()
                if op == '(':
                    break
                else:
                    output.append(op)
                    
        elif i in ['+','-','*','/','%']:
            while not st.emt():
                op = st.peek()
                if check(op) >= check(i):
                    output.append(st.pop())
                else:
                    break
            st.push(i)
        else:
            output.append(i)
    while not st.emt():
        output.append(st.pop())
    return output


string = input("input num : ")
string = re.split('([^0-9])',string)
string = ' '.join(string).split()
ans = inToPost(string)
for i in ans:
    print(i,end=" ")

숫자와 연산자를 구분하는 방법은 

> 여기에 < 설명되어있습니다.

 

 

🙋‍♂️ 후위표현식 계산하기

---

.
.
.

def postCal(formula):
    st = Stack()
    for i in formula:
        if i == '+':
            num1=st.pop()
            num2=st.pop()
            rst=int(num2)+int(num1)
            st.push(rst)
        elif i == '-':
            num1=st.pop()
            num2=st.pop()
            rst=int(num2)-int(num1)
            st.push(rst)
        elif i == '*':
            num1=st.pop()
            num2=st.pop()
            rst=int(num2)*int(num1)
            st.push(rst)
        elif i == '/':
            num1=st.pop()
            num2=st.pop()
            rst=int(num2)/int(num1)
            st.push(rst)
        elif i == '%':
            num1=st.pop()
            num2=st.pop()
            rst=int(num2)%int(num1)
            st.push(rst)
        else:
            st.push(i)
    return st.peek()
    
    .
    .
    .

rst = postCal(ans)
print(f'\n\nresult is {rst}')

간단합니다. 이 함수도 맨 위의 Stack class를 이용해서

if문으로 값을 구분하여 숫자면 stack에 넣고

연산자면 stack에서 값을 빼서 계산한 값을 stack에 넣도록 하면 됩니다.