[SWEA] 1224. [S/W 문제해결 기본] 6일차 - 계산기3 (python)

1) [SWEA] 1224. [S/W 문제해결 기본] 6일차 - 계산기3 (python)

문제 출처 : 

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14tDX6AFgCFAYD&categoryId=AV14tDX6AFgCFAYD&categoryType=CODE&problemTitle=%EA%B3%84%EC%82%B0%EA%B8%B03&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&&&&&&&&&&& 

SW Expert Academy

 

 

1) 계산기 2문제에서 괄호가 추가된 것

괄호가 시작됐다면 이 식을 먼저 수행해서 반영하겠다는 뜻이다. 

 

[1] 중위 표기식 -> 후위 표기식

후위 표기식으로 바꿔야 우선순위 등을 쉽게 처리 가능 

equ에는 후위 표기식을 저장할 변수

stk는 연산자의 스택으로 사용 

 

1) 숫자인 경우 : equ에 추가

2) 숫자가 아닌 경우 (else ) :

    1) 열린 괄호 == '(' #무조건 stk에 push 

    -> 스택 진입 시 우선순위가 가장 높아야하고

        스택에 저장된 상태에서는 가장 낮은 우선순위여야 한다. 

    2) 닫힌 괄호 == ')' #'(' 만날 때 까지 모두 pop해서 equ에 추가 

        이 때 '(' ')' equ 에 추가 되면 안된다. (당연) 

   else #연산자일 경우 

      while stk(스택에 데이터가 있고)  and pri[ch] <= pri[stk[-1]]

                  equ += stk.pop()

      stk.append(ch)

 

pri[ch] 는 incomingpriority 여야 하고 pri[stk[-1]]]은 instackpriority로 우선순위를 따진다.

 

모두 끝난후에는 stk에 남아있는 연산자를 모두 pop하여 equ에 추가

 

스택 내의 우선순위는 * : 2 , + : 1, '(' : 0 (보다 다른 우선순위가 더 크게 만들어준다. (가 움직이지 않고  자리 지켜주기 위함 

스택 진입 시 우선순위는 '(' : 3 , * : 2, +: 1 로 (가 무조건 push되게 해준다. 

 

동작 과정을 예시에 있는 “3+(4+5)*6+7” 로 해본다면

 

 

1) st의 3을 읽는다. 숫자이므로 바로 equ에 추가 

st = 3+(4+5)*6+7

 

equ  = 3 

stk = 

 

2) st의 +을 읽는다. 스택에 데이터가 없으므로 바로 stk에 push 

st = 3+(4+5)*6+7

 

equ  = 3 

stk =  +

 

3) st의 (을 읽는다. (이므로 +보다 우선순위가 높음 따라서 stk에 push 

st = 3+(4+5)*6+7

 

equ  = 3 

stk = + ( 

 

4) 연산자 이므로 equ에 추가 

st = 3+(4+5)*6+7

 

equ  = 3 4 

stk = + ( 

 

5) + 이므로 (보다 우선순위가 (보다 높음 따라서 그냥 push 

st = 3+(4+5)*6+7

 

equ  = 3 4 

stk = + (  + 

 

6) 5이므로 equ에 그냥 추가 

st = 3+(4+5)*6+7

 

equ  = 3 4 5

stk = + (  + 

 

7) )이므로 (만날 때 까지 pop 

st = 3+(4+5)*6+7

 

equ  = 3 4 5 + 

stk = + 

 

8) *므로 +보다 크므로 stk 에 추가 

st = 3+(4+5)*6+7

 

equ  = 3 4 5 + 

stk = + * 

9) 6이므로 equ에 추가 

st = 3+(4+5)*6+7

 

equ  = 3 4 5 + 6 

stk = + * 

 

10) +이므로 *보다 작음 따라서 while문 반복

*pop 되서 equ에 추가 

st = 3+(4+5)*6+7

 

+ pop되서 equ에 추가 

equ  = 3 4 5 + 6 * + 

 

그 후 + stk 에 추가 

stk = + 

 

11) 7이므로 equ에 추가 

 

equ  = 3 4 5 + 6 * + 7 

stk = +

 

12) stk에 남아있는 연산자들 다 poop

 

equ  = 3 4 5 + 6 * + 7 + 

stk = 

 

따라서 345+6*+7+이 나옴 

 

---

 

중위 표기법으로 표현된 산술식을 계산하는 계산기이다.

'icp'와 'isp' 연산자 딕셔너리를 초기화해주고 이 딕셔너리는 우선순위를 정의하는 것이다.

icp : incoming 즉, 스택에 push 할 때 연산자의 우선순위를 나타냄

isp : 스택에서 Pop할 때 연산자의 우선순위 즉, 스택 내에서의 우선순위이다.

 

st에서 중위 표기식을 저장할 변수, stk는 연산자 스택으로 사용, equ는 후위 표기식을 저장할 변수를 저장하는 데 사용

 

중위 표기식을 후위 표기식으로 변환

st의 각문자를 ch가 순회한다.

ch가 숫자인 경우 equ에 ch를 추가하고

ch가 연산자일 경우

    ) 인 경우 (가 나올 때 까지 스택에서 값을 꺼내 equ에 추가

    ( 가 아닌 다른 연산자인 경우 스택에 비어있지 않고 ch의 우선순위가 스택의 맨 위 연산자보다 작거나 같을 때 까지 스택에서 값을 꺼내       어 equ에 추가 반복문이 끝나면 ch를 스택에 Push 

스택에 남아있는 연산자를 equ에 추가

후위 표기식을 계산

equ의 문자 ch가 순회

ch가 숫자인 경우 stk에 ch를 정수형으로 변환 후 stk에 push

ch가 연산자일 경우 

stk 에서 op2 op1 pop 

그 후 + 면 + 연산, *면 * 연산

 

 

---

슈도 코드

icp = {'(' : 3, '*' : 2, '+' : 1 }  #스택 push 시 우선순위 연산자 딕셔너리
isp = {         '*' : 2, '+' : 1, '(' : 0 } #스택 내에서의 우선순위 연산자 딕셔너리 

각각의 테스트 케이스에 대해 반복 : 
	중위 표기시 입력받기
    후위 표기식 저장할 빈 문자열 equ 초기화
    스태 stk 초기화
    
    중위표기식을 후위표기식으로 변환 : 
    중위표기식의 각 문자 ch에 대해 반복 : 
    	ch가 숫자인 경우 : 
        	ch를 후위 표기식 equ에 추가 
        그렇지 않으면 : 
        	ch가 ')' 인 경우 : 
            	stk에서 '(' 나올 때 까지 연산자를 꺼내서 equ에 추가
            그렇지 않으면 : 
            	stk가 비어 있지 않고 stk의 맨 위 연산자의 스택 내 우선순위가 스택 밖 우선순위보다 작거나 같을 때 까지 
                연산자를 꺼내서 equ에 추가
                ch를 stk에 push 
            stk에 남아있는 모든 연산자를 equ에 추가 
            
            후위 표기식 게산 : 
            후위표기식의 각 문자 ch에 대한 반복 : 
            	ch가 숫자인 경우 : 
                	ch를 정수형으로 변환하여 stk에 push
                그렇지 않으면 : 
                	stk에서 상위 두 개의 피연산자 op2와 op1을 pop
                    결과를 stk에 push
            표현식의 결과, 즉 , stk의 맨위 요소를 출력

 

 

3)소스  코드

 

icp = {'(':3, '*':2, '+':1} #(가 최고 높아서 무조건 push 스택에 들어갈 때 우선순위(incoming)
isp = {       '*':2, '+':1, '(':0}  #낮게해서 (위로 연산자가 쌓이게 만듬 스택 내의 우선순위 (instack)
T=10


for test_case in range(1,T+1) :
    _ = input() #계속 꺼내 쓸 거니까 갯수가 필요없음
    st = input() #중위 표기식 입력받기

    equ = '' #후위표기식을 저장할 변수
    stk = [] #스택


    # [1] 중위 -> 후위
    for ch in st :
        if ch.isdigit(): #숫자일 경우
            equ+=ch #equ에 넣기
        else :  #연산자일 경우
            if ch == ')' : #닫는 괄호일 경우
                while stk : #stk를 순회
                    t = stk.pop()
                    if t == '(' :
                        break #저장하지 않고 종료
                    else :
                        equ+=t #equ에 괄호 내 연산자 넣기
            else : #연산자
                while stk and icp[ch] <= isp[stk[-1]] :
                    #스택이 비어있지 않고, instack 우선순위가 incoming 우선순위보다
                    #작거나 같은 동안 반복
                    equ += stk.pop()  #우선순위가 큰 연산자를 후위 표기식에 넣기
                stk.append(ch)

    while stk : #연산자가 스택에 남아있으므로
        equ += stk.pop()

    #[2] 후위 표기식 계산
    for ch in equ :
        if ch.isdigit() : #숫자인가?
            stk.append(int(ch)) #숫자로 변환하여 stk에 넣기
        else :
            op2 = stk.pop() #op1, 2 순서에 주의 !
            op1 = stk.pop()
            if ch == '*' :
                stk.append(op1*op2)
            elif ch == '+' :
                stk.append(op1+op2)

    print(f'#{test_case} {stk.pop()}') #stk에 결과가 있으므로 pop하기

 

 

---

TIL

1. 중위 표기식을 후위 표기식으로 변환하는 과정 : 

- 스택을 활용하여 연산자들을 올바른 순서로 정렬하여 후위 표기식으로 변환

- 스택은 연산자들의 우선순위를 비교하여 적절한 위치에 연산자를 쌓는 역할을 한다.

- 중위 표기식을 순회하면서 피연산자는 그대로 출력, 연산자는 스택과의 우선순위 비교를 통해 적절한 위치에 추가, 

- 이러한 변환 과정을 통해 중위표기식을 후위표기식으로 변환할 수 있다.

 

2. 후위 표기식을 계산하는 과정 :

- 후위 표기식은 피연산자와 연산자가 올바른 순서로 배열되어 있어 계산에 용이

- 스택을 활용하여 피연산자를 스택에 push, 연산자를 만나면 스택에서 필요한 개수의 피연산자를 pop하여 연산 수행

- 연산 결과를 다시 스택에 push하여 최종결과 얻기