스택을 이용한 중위 표기법, 후위 표기법 변환 및 계산

출처 : https://todaycode.tistory.com/73

중위 표기법과 후위 표기법

 

(1) 중위 표기법 -> 후위 표기법

1. 숫자는 그대로 출력

2. 연산이 나오면 스택에 넣기

2-1. 스택이 비어있다면 나온 바로 스택에 넣는다.

2-2. 스택의 top(peek)에 있는 연산자의 우선순위 < 현재 연산자 우선순위 라면 스택에 넣는다.

2-3. 현재 연산자의 우선순위가 더 작거나 같다면 스택이 비거나 , 현재 연산자 우선순위가 더 커질때까지 pop하여 연산을 출력한다. 그리고 현재 연산자를 스택에 넣는다.

3. 수식이 끝났다면 스택이 빌때까지 pop하여 출력

**우선순위는 (더하기=빼기) < (곱하기=나누기)이다.

 

-- 괄호가 나온다면?

4. 여는 괄호는 스택에 그냥 추가한다.

5. 여는 괄호 다음에 오는 연산자는 그냥 스택에 추가한다.

6. 닫는 괄호는 여는 괄호가 나올 때까지 스택을 pop 하여 출력한다. 다 출력하고 난 뒤 괄호들은 버린다.

 

 

Ex. A+B*C-D/E ==> ABC*+DE/-

 

 

(2) 후위 표기법 계산 방법

1. 숫자를 스택에 넣는다.

2. 연산자가 나오면 숫자 2개를 pop하여 계산하고 계산한 결과를 다시 스택에 넣는다.

** 먼저 pop되는 숫자가 2번째 값, 나중에 pop되는 숫자가 1번째 값이다.

Ex. AB- ==> A-B