2019.03.14 TIL-2
(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)
대답해보기
- class를 통해 stack 계산기를 구현했을 때의 장점
Stack을 활용한 계산기 구현
1.구현 목표
>>>계산할 값을 입력해주세요 : (2+5)\*3\*(2+1)
>>>25+3\*21+\* # 후위 표기법으로 입력
>>>63 # 정답 도출
우리가 일반적으로 사용하는 것은 중위 표기법이다.(2+5)*3*(2+1)
이것을 컴퓨터가 계산할 수 있는 후기표기법 (25+3*21+*)으로 변경하고
이후 결과값을 도출할 수 있도록 구현해야 한다.
조금 더 쉬운 구현을 위해 제한 조건을 둔다.
- 입력 받는 숫자는 1자리 숫자로 한정한다.(사용자가 알고 있어 따로 구현x)
- 정수 연산을 한다. 5/3 —> 1
위의 것을 구현하기 위해서는 크게 2가지를 먼저 알아야 한다.
- 중위표기법을 후위표기법으로 바꾸는 방법
- 후위표기법을 계산하는 방법.
따라서 먼저 위의 중위표기법을 후위표기법으로 바꾸는 방법 먼저 살표보자
중위표기법 —> 후위표기법
각 연산자마다 가중치가 있다.
- *, / : 가중치가 제일 크다. (10 or 100)
- , - : 가중치가 중간이다. (5 or 50)
- ( , ) : 가중치가 가장 작다.
일단 위의 조건 한개를 바탕으로 시작해야 한다.
이후 최종 후위 수식을 담을 수식 리스트와 연산자를 가중치에 따라 담을 스택 리스트가 필요하다.
ex) (2+5)\*3\*(2+1)
>>> list = [2,5,+,3,\,*,2,1,+,\,*] #수식리스트
>>> st = Stack() #연산자를 가중치에 따라 담을 스택리스트
>>>
연산자를 스택에 쌓는 조건
- ”(“ 는 무조건 쌓이고 이후에 오는 연산자가 가중치가 크면 쌓는다.
(힘이 쎄면 위를 덮어버린다.) - 이후에 오는 연산자의 가중치가 같거나 낮으면 수식리스트로 배출한다.
(단 수식리스트에 추가하고 또 그 아래에 있는 수식과 비교한다. peek을 통해 먼저 확인하고 뽑아야 하면 뽑아 내고 아니면 그냥 쌓는다.) - ”)”를 만나는 순간 ( 위에 있는 모든 연산자를 수식리스트에 넣고 (는 없앤다.(while문 활용, 나가는 순서대로 리스트에 추가)
- 즉 스택에 쌓이는 수식은 위로 갈수록 가중치가 높아야 한다.
- 마지막에는 while문을 통해 스택에 수식이 남아 있는지 없는지 꼭 확인을 한다. 남은 것은 다 while문을 돌아서 다 list에 넣어준다.
위를 기본조건으로 하여 연산자를 스택에 추가한다.
중위표기식을 읽어갈 때 숫자는 바로 수식리스트에 순서대로 추가한다
위의 내용을 통해 먼저 중위표기법을 후위표기법으로 만드는 알고리즘을 구현해본다.
의식의 흐름
- 먼저 input을 통해 중위표기법 식을 받는다.
- 숫자 및 수식 이외의 값을 입력하면 다시 입력하게 한다.
- 수식리스트를 만들고 수식의 가중치를 비교하고 스택에 쌓거나 배출하는 함수를 만든다.
- check —> input을 읽어와 숫자면 수식리스트로 넣고 수식이면 위에 만들어 놓은 함수를 불러온다.
- 완성된 수식리스트를 join을 통해 string으로 바꾸어 화면에 표기해준다.
–> 이렇게 하면 중위표기법을 후위표기법으로 변환시킬 수 있다.
input을 통해 중위 표기법 식을 받는다.
-> 숫자 및 수식 이외의 값을 입력하면 다시 입력하게 한다.
>>> Num_expression = ["1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "+", "-", "*", "/", "(", ")"]
>>> def input_expression():
>>> global Num_expression
>>> while True: #break가 나올 때까지 무한 루프
>>> get_input = input("식을 입력해주세요 : ")
>>> a = get_input.replace(" ","")
>>> flag = True
>>> for i in a:
>>> if i not in Num_expression:
>>> print("숫자 혹은 +,-,/,*,(,)만 입력해주세요")
>>> flag = False
>>> break #for문을 깨주는 break
>>> if flag:
>>> break #while문을 깨주는 break
>>> return a
>>>
—> for문을 통해 a의 요소 한개 한개를 다 비교하고 나중에 문제가 없을 때 return을 주기 위해 며칠동안 고민을 많이하였다. 하지만 간단하게 flag를 통해 해결 할 수 있다는 것을 깨달았다 ㅠㅠ…앞으로 잘 써먹어봐야겠다.
숫자리스트를 만들고 수식의 가중치를 비교하여 스택에 쌓거나 배출
>>> from stack import Stack
>>> St = Stack()
>>> calculate_li = []
>>> compare_weight = {"+": 3, "-": 3, "*": 5, "/": 5, "(": 1, ")": 1}
>>>
>>> def check_weight(a):
>>> global St
>>> global calculate_li
>>> global compare_weight
>>>
>>> if not St.empty():
>>> if a == "(": #"("면 무조건 스텍에 쌓는다.
>>> St.push(a)
>>> elif a == ")":
>>> while St.peek() != "(":
>>> calculate_li.append(St.pop())
>>> if St.peek() == "(":
>>> St.pop()
>>> break
>>>
>>> # 쌓인 스택과 들어갈 스택의 가중치를 비교하여 쌓거나 배출한다. 없으면 그대로 쌓는다.
>>> elif compare_weight[St.peek()] >= compare_weight[a]:
>>> while compare_weight[St.peek()] >= compare_weight[a]:
>>> calculate_li.append(St.pop()]
>>> if St.empty() == True:
>>> St.push(a)
>>> break
>>> else:
>>> St.push(a) #위의 elif에서 걸리게 되면 elif문에서 실행 뒤에 아래의 elif문으로는 내려가지 않는다.
>>>
>>> elif compare_weight[St.peek()] < compare_weight[a]:
>>> St.push(a)
>>>
>>> else: #만약에 stack이 비어있으면 그냥 바로 쌓는다.
>>> St.push(a)
>>>
한개의 if문 중에서 걸리게 되면 if문 실행 이후에 아래 elif문에서 조건이 성립하더라도 그냥 지나친다.
check —> input을 읽어와 숫자면 수식리스트로 넣고 수식이면 위에 만들어 놓은 함수를 불러온다.
- input을 실행시켜 숫자면 수식리스트에 넣고 수식이 아니면 위에 만들어 놓은 함수를 불러온다.
- 제일 마지막에 Stack에 남은 숫자 혹은 수식을 수식리스트에 넣도록 한다.
- 완성된 수식리스트를 join을 통해 string으로 바꾸어 화면에 표기에 준다.
>>> Num = ["1", "2", "3", "4", "5", "6", "7", "8", "9", "0"]. #나중에는 정규표현식을 쓰면 훨씬 간단해질 수 있다.
>>> expression = ["+", "-", "*", "/", "(", ")"]
>>>
>>> def check_expression():
>>> result = input_expression() #check_expression을 실행하면 input_expression()실행
>>> global calculate_li
>>> global Num
>>> global expression
>>> for i in result:
>>> if i in Num:
>>> calculate_li.append(i)
>>> elif i in expression:
>>> check_weight(i)
>>>
>>> while not St.empty(): #남은 스택을 돌며 수식리스트에 넣어준다.
>>> if St.peek() != "(":
>>> calculate_li.append(St.pop())
>>> elif St.peek() == "(":
>>> St.pop()
>>>
>>> print("".join(calculate_li)) #화면에 string으로 표기 되도록 한다.
>>> return calculate_li
>>>
후위표기법 –> 계산
- 후위표기식 계산 방법
- 앞에서부터 읽으면서 피연산자(숫자)는 스택(Stack)에 쌓는다.
- 연산자를 만나면 스택에서 피연산자 2개를 꺼내 연산을 수행하고 스택에 쌓는다.
- 1번과 2번을 끝날 때까지 반복한다.
- 이해가 안되시는 분은 구글에 후위표기법 계산을 검색해보면 바로 알 수 있습니다 :)
>>> def calculate(li): #마지막에 li에는 check_expression()이 들어가야 한다.
>>> global Num # class를 통해 구현하면 위와 같은 일을 하지 않아도 된다.
>>> global expression
>>> St1 = Stack()
>>> while li != []:
>>> if li[0] in Num:
>>> St1.push(int(li[0]))
>>> del li[0]
>>> elif li[0] in expression:
>>> a = int(St1.pop())
>>> b = int(St2.pop())
>>> if li[0] == "+":
>>> St1.push(b + a) # 연산 이후 다시 스택에 쌓아 준다.
>>> del li[0]
>>> elif li[0] == "-":
>>> St1.push(b - a)
>>> del li[0]
>>> elif li[0] == "*":
>>> St1.push(b * a)
>>> del li[0]
>>> elif li[0] == "/":
>>> St1.push(b // a)
>>> del li[0]
>>>
>>>
>>> print(St1.peek())
>>> return St1.pop()
>>>
>>>
식 실행시켜보기
>>> calculate(check_expression())
>>> 식을 넣어주세요 : 1+2+3+4
>>> 12+3+4+
>>> 10
>>>
>>> calculate(check_expression())
>>> 식을 넣어주세요 : 2+3!
>>> 숫자 or +,-,.,*,(,) 을 넣어주세요
>>> 식을 넣어주세요 : (3+4)*2/4
>>> 34+2*4
>>> 3
위와 같이 잘 나오는 것을 확인할 수 있다.
다음번에 해보기
- 클래스를 통해 위의 식을 구현해보자. 실행 이후 아래에 꼭 첨부해주기