2.1 후위표기식 (with Stack)

후위 표기식이란?

A x B + C
2 + 3 x 5
이와 같이 (피연산자)(연산자)(피연산자)의 순서로 두 피연산자 사이에 연산자를 표기하는 방법 을 중위표기법이라고 부른다.
그런데 컴퓨터에서 중위표기 수식을 순서대로 계산할 경우, 연산자의 우선순위를 고려하지 못 해 애로사항이 생기게 된다. 예를 들어 2+35의 경우, 연산이 우선순위가 있지만 +가 앞 에 있기 때문에 순서대로 계산하는 컴퓨터에서는 이를 적절하게 처리하기가 힘들다.
이 때문에 컴퓨터 프로그램에서는 수식 계산을 쉽게 하기 위하여 중위 표기된 수식을 다음과 같이 변환하여 사용한다.
A B x C +
2 3 5 x +
이처럼 (피연산자)(피연산자)(연산자)의 순서로 연산자의 우선순위를 고려하여 연산자를 피연산 자의 뒤에 표기하는 방법을 후위표기법이라고 부른다.

2023-1-w3p2 에서

그니까 무슨소리냐면

A + B + C = AB+C+
A랑 B더하고 C 더한다고
AB*C- = ?
A랑 B곱하고 C 뺀다고

예제 1

35+ = ?
34x = ?
23+ = ?
23x5+ = ?
452-+ = ?
36+67x- = ?
378+-2x = ?
357+2x+ = ?
3548--+ = ?
2023-1-w3p2 예제

3 + 5 = 8
3 * 4 = 12
2 + 3 = 5
2 * 3 + 5 = 11
4 + (5 - 2) = 7
(3 + 6) - (6 * 7) = -33
(3 - (7 + 8)) * 2 = -24
3 + ((5 + 7) * 2) = 27
3 + (5 - (4 - 8)) = 12

예제 2

1 - 2 + 3
1 x 2 - 3
2 x 3 + 5 x 6 - 7 + 3
7 + 8 x 9 - 2 x 3
6 x 4 - 1 x 4 x 1 - 5

1 2 - 3 +
1 2 * 3 -
2 3 * 5 6 * + 7 - 3 +
7 8 9 * + 2 3 * -
6 4 * 1 4 * 1 * - 5 -

그래서 이게 stack이랑 무슨 상관 인가여?

1 . 후위표기식 계산하기

357+2*+ 
= 3 + ((5 + 7) * 2) = 27

앞에서 부터 숫자면 push 연산기호면 pop 두번

push(3) -> push(5) -> push(7)
-> pop()-> pop()  // 7, 5
-> push(5+7) -> push(2) 
-> pop() -> pop() // 2, 12
-> push(12*2)
-> pop() -> pop() // 24, 3
= 3 + 24

2. 중위표기식 후위표기식으로 변경하기

2 * 3 + 5 * 6 - 7 + 3
= 2 3 * 5 6 * + 7 - 3 +

숫자면 그냥 출력
연산기호이면 top이 자기보다 우선순위 높으면 pop 그리고 push
마지막엔 스택에 있는거 전부 pop

// 2
push(*)
// 23
-> pop() 
// 23*
-> push(+) 
// 23*5
-> push(*)
// 23*56
-> pop()
// 23*56*
-> pop()
// 23*56*+
-> push(-)
// 23*56*+7
-> pop()
// 23*56*+7-
-> push(+)
// 23*56*+7-3
-> pop()
// 23*56*+7-3+