[Java] 스택(Stack) 2편 : 수식의 표기법

 

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다.

 

 

 

 

수식의 표기법

 

• 프로그램을 작성할 때 수식에서 +, -, * , / 와 같은 이항 연산자는 2개의 피연산자 사이에 위치 : 중위 표기(Infix Notation)
• 컴파일러는 중위 표기 수식을 후위 표기(Postfix Notation)으로 바꾼다.
  • 그 이유는 후위 표기법 수식은 괄호 없이 중위 표기 수식을 표현할 수 있기 때문
• 전위 표기(Prefix Notation) : 연산자를 피연산자들 앞에 두는 표기

 

중위 표기 수식에 대으되는 후위 표기, 전위 표기 수식

 

 

후위 표기 수식 계산

 

<<아이디어>>
피연산자는 스택에 push하고, 연산자는 2회 pop하여 계산한 후 push

 

 

 

 

후위표기로 표현된 수식 계산 알고리즘

 

입력을 좌에서 우로 문자를 1개씩 읽고 이를  C라고 하면

1. C가 피연산자라면 C를 push
2. C가 연산자(op)면 pop을 2회 수행. 먼저 pop된 피연산자가 A이고, 나중에 pop된 피연산자가 B라면, (A op B)를 수해앟여 그 결괏값을 push

Exempli Gratia

 

 

중위 수식을 후위 표기로 변환하는 알고리즘

 

<<아이디어>>
왼쪽 괄호나 연산자는 스택에 push하고, 피연산자는 출력

 

 

• 입력을 좌에서 우로 문자를 1개씩 읽는다. 그 읽은 문자의 경우가 아래와 같다면

1. 피연산자면, 읽은 문잘르 출력
2. 왼쪽 괄호이면, push
3. 오른쪽 괄호이면, 왼쪽 괄호가 나올 때까지  pop하여 출력. 단, 오른쪽이나 왼쪽 괄호는 출력하지 않는다.
4. 연산자이면, 자신의 우선순위보다 낮은 연산자간 스택 top에 나타날 때까지 pop하여 출력하고 읽은 연산자를 push

 

• 입력을 모두 읽었으면 스택이 empty될 때까지 pop 출력

exempli gratia