후위 표기식 변환 및 계산 알고리즘

수식 표기 방법

수식 표기 방법에는 전위, 중위, 후위 표기법이 있다. 우리가 일반적으로 사용하는 표기법은 중위 표기법이다.

• 중위 표기법: 연산자가 피연산자 가운데 위치.

• 전위 표기법: 연산자가 피연산자 앞에 위치.

• 후위 표기법: 연산자가 피연산자 뒤에 위치.

중위 표기법	전위 표기법	후위 표기법
1+3*8	+1*38	138*+
2*5-7	-*257	25*7-
(a+b)+4	++ab4	ab+4+

---

컴퓨터에서 수식을 계산하는 순서

1. 중위 표기식을 후위 표기식으로 변환
2. 후위 표기식을 계산

1, 2단계 모두에서 스택을 활용한다.

---

중위 표기식에서 후위 표기식으로 변환

중위표기식과 후위표기식의 공통점은 피연산자의 순서가 동일하다는 것이다.
둘은 연산자 순서만 다르다. 연산자만 스택을 활용해 저장했다가 출력하면 된다.

<알고리즘>

- 피연산자를 만나면 그대로 출력
- 연산자를 만나면 스택 상단의 연산자와 비교
    > 지금 넣으려는 연산자의 우선 순위가 더 크면 해당 연산자를 스택에 삽입
    > 작거나 같으면 스택 상단의 연산자를 출력하고 다시 반복
- 왼쪽 괄호가 나오면 스택에 삽입
- 오른쪽 괄호가 나오면 스택에서 왼쪽 괄호가 나올때까지 모든 연산자 pop(삭제와 출력). 왼쪽 괄호는 삭제
- 처리할 문자가 표기식에 남아있지 않다면 스택에 남아있는 모든 연산자 pop(삭제와 출력)

c++로 구현한 후위 표기식 변환 알고리즘 바로가기

백준 1918: 후위 표기식 (C++)

 

예시) (a+f(b^d^g))/(a+b)d+e%c 을 후위 표기식으로 변환하는 과정은 아래와 같다.

---

후위 표기식 계산

수식을 왼쪽에서 오른쪽으로 스캔하면서

- 피연산자면 스택에 저장

- 연산자면 필요한 수만큼의 피연산자를 스택에 꺼내서 연산을 실행하고 연산 결과를 다시 스택에 저장

하는 과정을 반복한다.

마지막에 스택에 남아있는 값이 연산 결과값이다.

 

예) 8 2 / 3 - 3 2 * + (중위 표기식: 8 / 2 - 3 + 3 * 2)