반응형
stack으로 계산기 구현하기
why 계산기 구현?
- 중위 표기법 수식을 스택을 이용하여 후위 표기법으로 변경할 수 있음
- 계산기 입장에서 계산이 쉬워져 속도 ↑
중위 표기법
- 연산자를 피연산자의 가운데에 표기하는 일반적인 방법
- ex) A+B , 2+3*4,
- 인간에게 친숙한 표현법
반응형
후위 표기법
- 컴퓨터의 입장에서 중위 표기법보다 후위 표기법이 더 쉬움
- 연산자가 나오면 이전 숫자 2개와 연산을 하는 방식
- ex) 2 3 4*+ → 2 12 + → 14의 과정으로 계산
- A*B-C/D을 후위 표기법으로 변환 방법
- ((A*B)-(C/D)) // 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현
- ((AB)*(CD)/)- // 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동
- AB*CD/- // 괄호 제거
변환 과정
- 입력 받은 중위표기식을 읽음
- 읽은 표기식이 피연산자이면 피연산자 출력
- 읽은 표기식이 연산자(괄호포함)일 경우 우선순위에 따라 분류
- 우선 순위가 높으면 → 스택에 psuh
- 우선 순위가 낮으면 → 연산자의 우선순위가 읽은 표기식의 우선순위보다 작아질 때까지 스택에서 pop한 후 연산자를 push
- 만약 top에 연산자가 없을 경우 → push
- 읽은 표기식이 )일 경우
- 스택 top에 (가 올 때까지 스택에 pop 수행
- pop한 연산자 출력
- (를 만나면 pop만 하고 출력하지 않음
- 중위표기식에 더 읽을 것이 없을 때까지 반복
- 스택에 남아 있는 연산자를 모두 pop하여 출력 (스택 밖 (가 우선 순위가 가장 높고 스택 안의 (가 우선 순위가 가장 낮음)
중위표기법을 후위 표기법으로 바꾸기 위한 코드
def suf_change(n) :
stack = []
result = ''
for i in n:
if i == '+' or i == '-': #우선순위 1 / 1
while stack and stack[-1] != '(':
result += stack.pop()
stack.append(i)
elif i == '*' or i == '/': #우선순위 2 / 2
while stack and (stack[-1] == '*' or stack[-1] == '/'):
result += stack.pop()
stack.append(i)
elif i == '(': #우선순위 0 / 3
stack.append(i)
elif i == ')': #(를 만날때까지 모두 pop
while stack and stack[-1] != '(':
result += stack.pop()
stack.pop()
else:
result += i
while stack:
result += stack.pop()
return result
print(suf_change(input()))
후위표기법 계산기 구현 코드
def Calculation(x):
stack = []
for i in x:
if i == '+':
stack.append(stack.pop()+stack.pop())
elif i == '-':
stack.append(-(stack.pop()-stack.pop()))
elif i == '*':
stack.append(stack.pop()*stack.pop())
elif i == '/':
divide = stack.pop()
stack.append(stack.pop()/divide)
else:
stack.append(int(i))
return stack.pop()
—> eval() 내장 함수를 이용하여 계산할 수도 있음
반응형
'언어별 개념 정리 > Python' 카테고리의 다른 글
[파이썬] 부분집합을 구하는 방법 (0) | 2023.02.12 |
---|---|
[파이썬] 정렬 알고리즘 - 버블 정렬 & 카운팅 정렬 (0) | 2023.02.12 |
[파이썬] 문자열(String) 알고리즘 정리 - 보이어 무어(Boyer-moore) 알고리즘 (0) | 2023.02.07 |
[파이썬] 문자열(String) 알고리즘 정리 - 브루트 포스(brute force) (0) | 2023.02.06 |
[파이썬] 알고리즘 풀이에 자주 사용되는 python 함수 및 알고리즘 기술 정리하기 (0) | 2023.02.05 |
댓글