크래프톤정글 2주차; 중위 표기식과 후위 표기식, 스택으로 계산기 구현

2022-11-09

중위 표기식과 후위 표기식의 개념, 스택으로 계산기 구현하기

출처: https://www.youtube.com/watch?v=G9ujrSGEB4A&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=10
https://www.youtube.com/watch?v=MYk4autDAJ0&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=10

무엇?

• 연산자 operator
• 피연산자 operand
• 토큰 token : 코드 상에서 연산자와 피연산자를 의미
• 이항연산자 binary operator: 2+3, 2*5처럼 두 수를 필요로 하는 연산자
• 단항연산자 unary operator: +3 같은 경우
• infix 수식: 연산자가 피연산자 사이에 있는 수식 형식, 일반적으로 일상에서 사용하는 수식
• postfix 수식: 연산자가 피연산자 오른쪽에 나타나는 수식 형식
  • 우선순위가 있는 계산이 용이함
  • 포스트픽스에는 괄호가 없음
• prefix 수식: 연산자가 피연산자 왼쪽에 나타나는 수식 형식, 포스트픽스와 대칭 이건 언제쓸까…?

왜?

코치님이 내주시는 매주 미션 中 하나
스택 구조를 이해하는데 도움

어떻게?

• 이항연산자만 사용한다고 가정
• infix -> postfix로 바꾸는 방법
  1. 우선순위에 따라 괄호치기
     • ex: (2+(3*5))
  2. 연산자의 오른쪽 괄호 다음으로 연산자 이동
     • ex: (2(35)*)+
  3. 첫번째 단계에서 쳐진 괄호를 모두 지움
     • ex: 235*+
• 이렇게 인픽스를 포스트픽스로 바꿀때 스택을 사용
  • 변수
    • 아웃스택 리스트 outstack : 포스트픽스로 출력 될 값을 담은 리스트(굳이 스택일 필요 없음)
    • 스택 opstack : 연산자들이 담길 스택
  • 입출력
    • 입력(토큰): +, -, *, /, (, ), 숫자(영문자)로 구성된 infix 수식
    • 출력: postfix 수식
  • 규칙
    1. 피연산자의 순서는 그대로임
    2. 연산자는 자기보다 우선순위가 낮은 연산자가 나올 때 포스트픽스로써 나감(그때까지는 어디선가 기다림 → 스택에서!)
    3. 연산자 중 이미 지나쳐 온 해당 연산자보다 우선순위가 높은 애들은 전부 다 pop 시킴
    4. 피연산자가 다 나왔으면 스택에 남아있는 연산자를 모두 pop 시킴 (스택의 pop임)
    5. 괄호의 우선 순위는, 닫는 괄호가 어떤 연산자보다 파워가 제일 셈
       1. 여는 괄호는 '괄호 안’의 모든 연산자보다 우선순위가 낮고, 닫는 괄호가 나올 때까지 스택에서 대기
       2. 닫는 괄호가 등장하면 이미 스택에 담겨진 여는 괄호를 만날 때까지 모든 연산자 팝 → 괄호 안의 연산을 가장 먼저 하게 됨
  • 슈도코드

  for each token in expr:
  	if token == operand:
  		outstack.append(token)
  	if token == '(':
  		opstack.push(token)
  	if token == ')':
  		while '('를 팝할 때까지:
  			opstack.pop()
  			outstack.append(pop된 것)
  	if token in ['+*-/']:
  		opstack에 token보다 우선순위 높은 연산자 모두 pop
  		opstack.push(token)
  opstack에 남은 연산자 모두 pop -> outstack.append()
  print(outstack)
  

• 포스트픽스를 결과값으로 계산하기
  • 변수
    • 피연산자 스택 s
  • 규칙
    1. 피연산자(숫자, 영문자 등)는 스택에 담음
    2. 연산자가 등장하면 피연산자 스택에 팝을 두 번하고(이항연산이기 때문?) 해당 연산자로 값 계산(이때 먼저 들어간 애를 좌항에 놓는 것이 맞지 않나)
    3. 계산한 값을 다시 피연산자 스택에 push
  • 슈도코드

if token == operand:
    s.push(token)
if token in ['+-*/']
    a = s.pop()
    b = s.pop()
    result = b, a를 token 연산자로 계산(ex: 빼기인 경우 b-a)
    s.push(result)
최종계산값 = s[0]  # 피연산자 스택에 남아있는 마지막 원소