전위 표기식, 중위 표기식, 후위 표기식에 관한 문제이다.
BOJ에도 비슷한 문제가 있다.(https://www.acmicpc.net/problem/1935, https://www.acmicpc.net/problem/1918)
전위 표기식은 연산자가 피연산자 앞에 오는 표기법이다(+AB)
중위 표기식은 일반적으로 쓰는 표기방법이다(A+B)
후위 표기식은 연산자가 피연산자의 뒤에 오는 표기방법이다.(AB+)
중위 표기식을 후위 표기식으로 바꾸어 계산한다.
들어가기 전 연산자 우선순위를 고려해야 한다.
1순위 : ( )
2순위 : * /
3순위 : + -
(4-(1+3)*2)+(4/2)
1. 숫자가 나오면 그대로 출력한다.
2. 1순위인 여는 괄호가 나오면 스택에 넣는다.
3. 2순위인 *, /가 나오면 스택에 넣는다.
4. 3순위인 +, - 연산이 나오면 여는 괄호, 여는 괄호가 으면 스택의 끝까지 출력하고 해당 연산자를 스택에 넣는다.
5. 닫는 괄호가 나오면 스택에서 여는 괄호가 나올때까지 pop한다.
결과 : 413+2*-42/+
예제 : (4-(1+3)*2)+(4/2)
계산결과 : -2
예제를 가지고 전위 표기식, 후위 표기식을 만들어준다
---------------------------- 계산법 ----------------------------
전위 표기법 : +-4*+132/42
전위 표기법은 스택의 peek와 현재 값이 숫자이면
스택의 값을 꺼낸 후 스택의 peek가 연산자이면 연산자에 따라 두 값을 계산 후에 다시 스택이 넣어준다.
두 수가 연속적으로 나오기 전 까지 연산자와 숫자를 스택에 계속 삽입한다. 스택의 방향은 [] < 오른쪽이 입구이다.
1. [ +, -, 4, *, + , 1 ]
+-4*+132/42
^ 현재 값
2. 스택의 peek가 1이고 현재 값이 3이니 스택의 1을 꺼내 임시값에 저장한다. [ +, -, 4, *, + ]
current = 3, temp = 1
스택의 peek가 +연산이니 두 값을 더하고 연산자를 pop시킨 후 더한 값인 4를 다시 스택에 넣는다.
[ +, -, 4, *, 4 ]
+-4*+132/42
^ 현재 값
3. 스택의 peek가 4이고 현재 값이 2이니 스택의 4를 꺼내 임시값에 저장한다. [ +, -, 4, * ]
current = 2, temp = 4
스택의 peek가 * 연산이니 두 값을 곱하고 연산자를 pop 후 곱한 값인 8을 스택에 넣는다
[ +, -, 4, 8]
+-4*+132/42
^ 현재 값
4. 현재 값이 연산자니 스택에 넣는다
[ +, -, 4, 8, / ]
+-4*+132/42
^ 현재값
5. 스택의 peek가 연산자고 현재 값이 숫자니 스택에 넣는다
[ +, -, 4, 8, /, 4 ]
+-4*+132/42
^ 현재 값
6. 스택의 peek가 4이고 현재값이 2이니 스택의 4를 꺼내 임시값에 저장한다. [ +, -, 4, 8, / ]
current = 2, temp = 4
스택의 peek가 / 연산이니 두 값을 나누고 연산자를 pop한 후 나눈 값인 2를 스택에 넣는다.
[ +, -, 4, 8, 2]
7. 계산식의 순회가 끝났으니 스택의 남은 값을 가지고 계산을 마저 한다.
7.1 임시 스택 하나를 만든다. []
7.2 기존 스택에서 연산자가 나올때 까지 값을 임시 스택으로 옮긴다.
[ +, - ], [ 4, 8, 2 ]
7.3 기존 스택에서 연산자가 발견되면 임시 스택에 있는 숫자를 두 개 빼고 연산자에 맞춰 계산을 한다. 계산 후 연산자는 pop하고 계산된 값은 임시 스택에 다시 넣는다. 계산은 꺼낸 값 순서대로 계산한다.
2 - 8 = -6, -> [ + ], [ 4, -6 ]
7.4 스택이 빌 때 까지 7.2, 7.3을 반복한다.
4 + (-6) = -2, [], []
결과 : -2
후위 표기법 : 413+2*-42/+
전위 표기법과 비슷하다. 전위 표기법은 현재 값과 스택의 끝이 숫자인지 비교했다면, 후위 표기법은 현재 값이 연산자인지 아닌지 판단한다.
1. 연산자가 오기 전까지 스택에 값을 넣는다.
[ 4, 1, 3 ]
413+2*-42/+
^ 현재 값
2. 연산자가 나오면 스택의 값 두개를 빼 연산 후 다시 넣어준다.
LIFO니 먼저 들어간 1이 앞에 오고 나중에 들어간 3이 뒤에 와야 한다.
1 + 3 = 4
[ 4, 4 ]
413+2*-42/+
^ 현재 값
3. 현재 값이 2이니 스택에 넣는다.
[ 4, 4, 2 ]
413+2*-42/+
^ 현재 값
4. 현재 값이 연산자니 스택의 두 값을 빼서 연산 후 스택에 다시 넣어준다. 4 + 2 = 8
[ 4, 8 ]
413+2*-42/+
^ 현재 값
5. 현재 값이 연산자니 스택의 두 값을 빼서 연산 후 스택에 다시 넣어준다. 4 - 8 = -4
[ -4 ]
413+2*-42/+
^ 현재 값
6. 뒤에 오는 숫자는 계속 스택에 넣어준다.
[ -4, 4, 2 ]
413+2*-42/+
^ 현재 값
7. 현재 값이 연산자니 스택의 두 값을 빼서 연산 후 스택에 다시 넣어준다. 4 / 2 = 2
[ -4, 2]
413+2*-42/+
^ 현재 값
8. 현재 값이 연산자니 스택의 두 값을 빼서 연산 후 스택에 다시 넣어준다. -4 + 2 = -2
[ -2 ]
9. 다음에 올 값이 없고, 스택의 크기가 1이니 계산이 끝났다.
답 : -2