[Python] 스택 응용 : 후위 표기법 이용한 수식 계산

2023.09.15 - [C/알고리즘] - 스택 응용(수식 계산)

스택 응용(수식 계산)

=> 수식 계산 알고리즘의 자세한 동작 과정은 위의 글에 상세히 적어두었다

 

1. 중위 표기 => 후위 표기 변환 연습

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 ch in S:
        if(ch in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'):
            answer+=ch
        elif(ch=='('):
            opStack.push(ch)
        elif(ch==')'):
            while(not opStack.isEmpty()):
                data = opStack.pop()
                if(data=='('):
                    break
                else:
                    answer+=data
        elif(ch=='+' or ch=='-' or ch=='/' or ch=='*'):
            while(not opStack.isEmpty()):
                data = opStack.peek()
                if(prec[data]<prec[ch]):
                    break
                else:
                    answer+=opStack.pop()
            opStack.push(ch)

    while(not opStack.isEmpty()):
          answer+= opStack.pop()

    return answer

 

 

2. 수식 계산 실전 연습

• splitTokens()
  : 문자열로 표현한 중위표기식 각각의 원소(숫자,괄호,연산자) 분리해서 반환하는 함수 
• infixToPostfix()
  : 중위표기식 후위표기식으로 변환
• postfixEval()
  : 후위표기식 통한 수식 계산

class Stack:

    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 ch in exprStr:
        if ch==' ':
            continue
        if ch in '0123456789':
            val = val*10 + int(ch)
            valProcessing = True 
        else:
            if valProcessing:
                tokens.append(val)
                val=0
            valProcessing=False
            tokens.append(ch)

    if valProcessing:
        tokens.append(val) 

    return tokens


def infixToPostfix(tokenList):
    prec={'*':3,'/':3,
          '+':2,'-':2,
          '(':1
          }
    
    opStack = Stack()
    postfixList=[]

    for token in tokenList:
        if type(token) is int:
            postfixList.append(token)
        elif token =='(':
            opStack.push(token)
        elif token ==')':
            while not opStack.isEmpty():
                data = opStack.pop()
                if(data=='('):
                    break
                else:
                    postfixList.append(data)

        else:
            while not opStack.isEmpty():
                data =opStack.peek()
                if(prec[data]<prec[token]):
                    break
                else:
                    postfixList.append(opStack.pop())
            
            opStack.push(token)

        
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    
    return postfixList


def postfixEval(tokenList):
    valStack = Stack()

    for token in tokenList:
        if type(token) is int:
            valStack.push(token)
        else:
            val1= valStack.pop()
            val2 = valStack.pop()
            if token =='*':
                valStack.push(val2*val1)
            elif token =='/':
                valStack.push(val2//val1)
            elif token =='+':
                valStack.push(val2+val1)
            elif token =='-':
                valStack.push(val2-val1)

    
    return valStack.pop()



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


print(solution('5 + 3')) #output : 8

 

cf> python 함수 이용하지 않고 스택 구현

class Stack:
    def __init__(self, size):
        self.data=[0]*size
        self.top=-1
        self.st_size=size
    
    def push(self,item):
        if(self.isFull()):
            return 'Full stack'
        
        else:
            self.top+=1
            self.data[self.top]=item

    def isEmpty(self):
        return self.top==-1
    
    def isFull(self):
        return self.top==self.st_size-1
    
    def peek(self):
        if(self.isEmpty()):
            return 'Empty stack'
        else:
            return self.data[self.top]
        
    def pop(self):
        if(self.isEmpty()):
            return 'Empty stack'
        else:
            item = self.data[self.top]
            self.top-=1
            return item
        
    def printStack(self):
        if(self.isEmpty()):
            return 'Empty stack'
        else:
            for i in range(0,self.top+1):
                print(self.data[i], end=' ')
                if i is not self.top:
                    print(' -> ')


def splitToken(exp):
    
    token=[]
    valProcessing = False
    val=0
    for element in exp:
        if(element ==' '):
            continue
       
        if element in '0123456789':
            valProcessing = True
            val*=10
            val+=int(element)
        else:
            if valProcessing==True:
                token.append(val)
                val=0 
            valProcessing=False               
            token.append(element)

    if valProcessing:
        token.append(val)

    return token


def InfixToPostfix(token):
    prec={'(':0,
         '+':1,'-':1,
         '*':2,'/':2,'%':2
         }

    stack = Stack(20)
    result=[]

    for element in token:
        if(type(element) is int):
            result.append(element)
        elif(element =='('):
            stack.push(element)
        elif(element ==')'):
            while(not stack.isEmpty()):
                data = stack.pop()
                if(data=='('):
                    break
                else:
                    result.append(data)

        else:
            while(not stack.isEmpty()):
                data = stack.peek()
                if(prec[data]<prec[element]):
                    break
                else:
                    result.append(stack.pop())

            stack.push(element)



    while(not stack.isEmpty()):
        result.append(stack.pop())

    
    return result

def eval(exp):
    stack = Stack(20)
    for token in exp:
        if(type(token) is int):
            stack.push(token)
        else:
            data1= stack.pop()
            data2= stack.pop()
            if(token =='*'):
                stack.push(data2*data1)
            elif(token =='/'):
                stack.push(data2//data1)
            elif(token=='+'):
                stack.push(data2+data1)
            elif(token =='-'):
                stack.push(data2-data1)
            elif(token=='%'):
                stack.push(data2%data1)

    return stack.pop()





def main():
    eval_test = "123+456*(789+(90-80+20*5)-(30*20-10/5))"
    tokens=splitToken(eval_test)
    print(tokens)
    print(eval(InfixToPostfix(tokens)))
    




if __name__=="__main__":
    main()