알고리즘 - 후위 표기법 학습

후위 계산

ex) 2 5 + 3 2 1 + = 63

1. 25+에서 연산자 ‘+’를 만났을 때, 멈추고 2+5 실시
2. 73에서 연산자 ‘‘를 만났을 때, 멈추고 7×3 실시
3. 2121+에서 ‘+’ 앞에 두 숫자 2+1 실시
4. 213* 에서 21×3 실시

후위 표기법 계산 알고리즘

1. 피연산자(숫자)는 바로 stack에 담는다.
2. 연산자가 나오면, stack 맨 위 숫자를 뒤에 두고, 그 아래 숫자를 앞에 두어 서로 연산한다.

중위표기법 -> 후위표기법 변환 방법

ex) 중위 표기법 : (2 + 5) 3 (2 + 1) / 후위 표기법 : 2 5 + 3 2 1 +

1. listExp = []
2. stack에 ‘(‘를 쌓는다. -> stack = [‘(‘,]
3. 피연산자는 바로 수식 리스트로 이동 -> listExp = [2]
4. ‘(‘가 ‘+’보다 가중치가 낮으므로, ‘+’를 stack에 쌓는다. -> stack = [‘(‘, ‘+’]
5. 피연산자 5를 수식 리스트로 이동 -> listExp = [2, 5]
6. ‘)’를 만나는 순간 ‘(‘ 위에 있는 모든 연산자를 pop하여, 순서대로 수식 리스트로 이동시키고, ‘(‘는 버리고 ‘)’도 버린다. -> listExp = [2, 5, ‘+’], stack = []
7. stack에 ‘‘를 쌓는다. -> stack = [‘‘]
8. 피연산자 3을 수식 리스트로 이동 -> listExp = [2, 5, ‘+’, 3]
9. stack에 있는 ‘‘가 ‘‘보다 가중치가 높거나 같으므로, stack의 ‘‘를 수식리스트에 이동시킨다. -> listExp = [2, 5, ‘+’, 3, ‘‘], stack = [‘*’]
10. ‘(‘는 가중치에 상관없이 무조건 stack에 쌓는다. -> stack = [‘*’, ‘(‘]
11. 피연산자 2를 수식 리스트로 이동 -> listExp = [2, 5, ‘+’, 3, ‘*’, 2]
12. ‘+’가 ‘(‘보다 가중치가 높으므로 stack에 쌓는다. -> stack = [‘*’, ‘(‘, ‘+’]
13. 피연산자 1을 수식 리스트로 이동 -> listExp = [2, 5, ‘+’, 3, ‘*’, 2, 1]
14. ‘)’ 만나는 순간 ‘(‘ 위에 모든 연산자를 수식리스트에 이동시키고, ‘(‘ 제거 -> stack = [‘‘], listExp = [2, 5, ‘+’, 3, ‘‘, 2, 1, ‘+’]
15. stack에 남아있는 모든 연산자를 수식리스트로 이동 -> listExp = [2, 5, ‘+’, 3, ‘‘, 2, 1, ‘+’, ‘‘]