[JavaScript] 후위 연산 표시법

사직 연산 프로그램을 만들면서 후위연산 표시법으로 접근해야할 필요가 생겼다.
보통 우리가 사용하는 수식은 중위표시법으로 표현되는데 중위표기법은 연산자가 피연산자들의 사이에 위치하게 되고 후위 표시법은 연산자가 피연산자들 뒤에 위치하는 것이다.

중위 표현법

// 연산자가 피연산자들 사이에 위치
(A+B)*(C+D)

후위 표현법

// 연산자가 피연산자 뒤에 위치
AB+CD+*

중위 표기식을 후위 표기법으로 표현하기

먼저 후위 표기식을 만들기 위해 자료구조 스택이 사용된다.

1. 피연산자는 스택에 넣지 않고 그냥 출력한다.

2. 연산자는 스택이 비었으면 스택에 push한다. 

3. 연산자는 스택이 비어있지 않으면 스택에 있는 연산자와의 우선순위를 비교해 스택에 있는 연산자의 우선순위가 같거나 크다면 스택에 있는 연산자를 pop을 한 후 출력하고 현재 연산자는 스택에 push한다.

4. 만약 3번에서 우선순위가 현재 연산자가 더 크면 현재 연산자를 push한다.(스택에서 pop하지 않음)

5. 수식이 끝나면 스택이 빌 때 까지 pop을 한 후 출력한다.

1. A는 피연산자이므로 (Result에)출력한다.
2. • 는 연산자인데, 현재 스택이 비었으므로 push한다.
3. B는 피연산자이므로 출력한다.
4. • 와 + 의 우선순위를 비교했을 때, *가 더 크므로 스택에 push한다. 
5. C는 피연산자이므로 출력한다.
6. 수식이 끝났으므로 스택에 있는 연산자들을 모두 pop하고 출력한다.
7. 식 완성! Result = ABC*+

괄호가 추가된 수식을 후위 표기법으로

1. 괄호가 여는 괄호이면 무조건 push한다.

2. 괄호가 닫는 괄호이면 stack에서 여는 괄호가 나올 때 까지 pop을 한 후 출력한다. 

3. 여는 괄호가 스택에 push된 후 닫는 괄호가 나올 때 까지 여는 괄호가 pop이 되면 안되므로 여는 괄호의 우선순위는 제일 작다. (위의 간단한 후위 표기법 알고리즘 3번 조건)   

4. 괄호는 출력하지 않는다.

1. 여는 괄호는 무조건 스택에 push한다.
2. A는 피연산자이므로 출력한다.
3. 연산자 우선순위를 비교했을 때 여는 괄호의 우선순위가 작으므로 +는 push 된다.
4. B는 피연산자이므로 출력한다.
5. 닫는 괄호가 나왔으므로 여는 괄호가 나올 때 까지 pop을 하고 출력한다. (괄호 제외) 
6. 스택이 비었으므로 연산자를 push한다.

7. 여는 괄호는 무조건 push.
8. C는 피연산자이므로 출력한다.
9. 연산자 우선순위를 비교했을 때 여는 괄호의 우선순위가 작으므로 +는 push 된다.
10. D는 피연산자이므로 출력한다.
11. 닫는 괄호가 나왔으므로 여는 괄호가 나올 때 까지 pop을 하고 출력한다. 
12. 수식이 끝났으므로 스택에 있는 연산자들을 모두 pop하고 출력한다. 

Reference

스택을 이용한 계산기 만들기
사칙연산 계산기 구현