지난번에 포스팅한 스택 자료구조를 활용하여 수식의 후위 표기법을 구현해보도록 하겠습니다!

스택의 응용 - 수식의 후위 표기법

• 중위 표기법 (infix notation): 연산자가 피연산자들의 사이에 위치
  • (A + B) * (C + D)
• 후위 표기법 (postfix notation): 연산자가 피연산자들의 뒤에 위치
  • AB+CD+*
  • 괄호가 사라지고 연산자들은 순서대로 연산

중위 표현식 -> 후위 표현식

• 중위: A * B + C
• 후위: AB*C+

• 피연산자는 그냥 쓰고 연산자를 만나면 Stack에 push
• 연산자를 만났는데 stack이 비어있지 않으면 stack의 마지막 연산자와 우선순위를 비교
  • stack에 있는 연산자의 우선순위가 높으면 pop으로 연산자 빼내기
  • 남은 연산자는 stack에 push
• 수식에 끝까지 왔으면 스택에 남아 있는 원소를 모두 pop

• 중위: A + B * C
• 후위: ABC * +

• 피연산자는 그냥 쓴다.
• 연산자를 만났을 때 stack이 비어 있으면 해당 연산자를 push
• 연산자를 만났는데 syack이 비어있지 않으면 stack의 마지막 연산자와 우선순위를 비교
  • stack에 있는 연산자보다 해당 연산자가 우선순위가 높으면 stack에 push
• 수식에 끝까지 왔으면 스택에 있는 모든 원소를 모두 pop

• 중위: A+B+C
• 후위: AB+C+

• 피연산자는 그냥 쓴다.
• 연산자를 만났을 때 stack이 비어 있으면 해당 연산자를 push
• 연산자를 만났는데 syack이 비어있지 않으면 stack의 마지막 연산자와 우선순위를 비교
  • stack에 있는 연산자보다 해당 연산자가 우선순위가 동일하면 stack에 있는 연산자 pop
  • 그 후 남은 연산자는 stack에 push
• 수식에 끝까지 왔으면 스택에 남아 있는 원소를 모두 pop

괄호의 처리

• 중위: (A + B) * C
• 후위: AB+C*

• 여는 괄호는 스택에 push
• 닫는 괄호를 만나면 여는 괄호가 나올때 까지 pop

• 중위: A * (B + C)
• 후위: ABC+*

연산자를 만났을 때, 여는 괄호 너머까지 pop하지 않도록
여는 괄호의 우선순위는 가장 낮게 설정

• 스택안에 상황: [*,(,+]

예제

• 중위: (A+B)*(C+D)
• 후위: AB+CD+*

• 중위: (A+(B-C))*D
• 후위: ABC-+D*

• 중위: A*(B-(C+D))
• 후위: ABCD+-*

알고리즘의 설계

(1) 연산자의 우선순위 설정

prec = {
	'*':3, '/':3,
    '+':2, '-':2,
    '(':1
}

(2) 중위 표현식을 왼쪽부터 한 글자씩 읽어서

• 피연산자이면 그냥 출력
• '('이면 스택에 push
• ')'이면 '('이 나올 때까지 스택에서 pop, 출력
• 연산자이면 스택에서 이보다 높(거나 같)은 우선순위 것들을 pop, 출력
  • 그리고 이 연산자는 스택에 push

(3) 스택에 남아 있는 연산자는 모두 pop, 출력

코드의 구현 - 힌트

• 스택의 맨 위에 있는 연산자와의 우선순위 비교
  • 스택의 peek() 연산 이용
• 스택에 남아 있는 연산자 모두 pop()하는 순화문
  • while noe opStack.isEmpty():