(파이썬)백준 알고리즘 1287번 할 수 있다

백준 알고리즘 저지 1287번 문제 (https://www.acmicpc.net/problem/1287)

 

 

연산자의 우선순위와 스택을 이용한 구현

후위 표현식의 꼴로 바꿔서 계산기를 구현했고 발견된 연산자가 기존 연산자보다 우선순위가 높을 경우 연산?이 발생함.

 

작성당시 참고한 사이트가 있었는데 못찾겠음

 

 

 
def rank(op):
    if op == '(':
        if flag==0:
            return 20
        else :
            return 0
    elif op == ')':return 19
    elif op in '*/':return 15
    elif op in '+-':return 14

def calc(A,B,op):
    if op=='+':
        return A+B
    elif op=='-':
        return A-B
    elif op=='*':
        return A*B
    elif op=='/':
        sA=str(A)
        sB=str(B)
        if len(sA)-len(sB)>15:
            real=A//B
            #asdf=
        return A//B

flag=0
input=input()#'1+(3-(+2+4))'#1*(2+3)
origin=[]
stackA=[]
stackB=[]
text=''
op=1
try:
    for i in input:#토크나이저
        if i in '+-*/()':
            if text!='':#이걸로 ()의 예외 제어
                origin.append(int(text))
            origin.append(i)
            text=''
        else :
            text+=i
    if text!='':
        origin.append(int(text))
    ###############################print(origin)
    '''
    5*(6*7+8)

    5 6 7 * 8 + *

    5 6 7 * 8
    * ( +      )
+(1+2+(2+3)
    (5*6)+3
    5 6 *
    (      )
    5 6 * 3 +
    '''
    for i in origin:
        #print(i)
        if op>=2 or op==-1 : print(10/0)
        if type(i)==type(1):
            op-=1
            stackA.append(i)
        else:

            if i=='(':
                if op==0:print(10/0)
                stackB.append(i)
                flag+=1
            elif i==')':
                if op==1:print(10/0)
                flag-=1
                #print(stackB)
                while stackB[len(stackB)-1]!='(':
                    stackA.append(stackB.pop())
                stackB.pop()
            elif len(stackB) <= 0:
                op+=1
                stackB.append(i)
            else :
                op+=1
                if rank(stackB[len(stackB)-1])>=rank(i):
                    stackA.append(stackB.pop())
                    stackB.append(i)
                else:
                    stackB.append(i)

    del(origin)#메모리확보
    '''
    for i in origin:
        #print(i)
        if type(i)==type(1):
            stackA.append(i)
        else :
            if len(stackB)<=0 :
                stackB.append(i)
                #print(i)
            else:
                if rank(stackB[len(stackB)-1])>=rank(i):
                    stackA.append(stackB.pop())
                    stackB.append(i)
                else:
                    stackB.append(i)
    '''
    #print(stackA)
    #print(stackB)
    while stackB:stackA.append(stackB.pop())
    ##############################print(stackA)

    for i in stackA:#stackB를 결과로 재활용
        if type(i)==type(1):
            stackB.append(i)
        else:
            B=stackB.pop()
            A=stackB.pop()
            stackB.append(calc(A,B,i))
    del(stackA)
    #print(9999999999999999999999999999999999999999999999999999999999999999999999999999999999/9)
    print(stackB.pop())

except:
    print('ROCK')