반응형
중위 표기식은 a+b 처럼 연산자가 가운데에 오는 평상시에 쓰는 식의 형태를 말한다.
그렇다면 전위, 후위 연산은 무엇일까?
설명
a=0, b=0, c=0
++a (a=1)
b++ (b=1)
c = ++a (a=2, c=2) ... a 증가 -> c에 대입
c = b++ (b=2, c=1) ... c에 대입 -> b 증가
c = (a++)+(++b) (a=3, b=3, c=5) ... b 증가 -> 덧셈 -> c 대입 -> a 증가
1. PostFixNotation
중위 표기식의 한계
사람이 사용하는 중위 표기식 계산은 컴퓨터 계산으로 활용하기 힘들다.
계산식의 우선순위를 논리적으로 판단하기 힘들기 때문이다.
그로 인해 후위 표기 방법을 사용하며, 중위 표기식을 후위 표기로 변환하는 알고리즘들이 만들어진다.
그 중 하나인 다익스트라가 고안한 방법을 포스팅 합니다.
위에서 우선순위 판단이 힘들어 중위 표기를 후위 표기로 변환하여 계산한다고 했습니다.
예로 확인하겠습니다.
계산식1 : 1+2+3+4 -> 우선 순위가 없으므로 계산에 문제 없음.
계산식2 : 1+2*3+4 -> 곱하기 연산을 먼저 계산하여야 한다.
계산식3 : 1+(2*3-(4-2)+3) -> 괄호부터 연산하여야 한다.
‘계산식 1’의 경우 우선 순위가 없으므로 순차적으로 계산함에 있어 아무런 문제도 없다.
하지만 ‘계산식2’의 경우 *를 먼저 연산하여야 한다. 물론 조건문을 잘 이용하면 계산이 가능하다. 하지만 ‘계산식 3’처럼 우선순위가 점점 복잡해지면 중위 표기방식으로 계산하기 매우 힘들어지게 된다.
그래서 이를 후위 표기식으로 변환하여 연산을 한다.
‘계산식3’을 후위표기식으로 변환하면 아래와 같다.
Postfix 계산식의 연산과정
가. 가장 앞에 위치한 연산자를 찾는다.
나. 연산자 앞 피연산자1, 피연산자2를 연산한다.
다. 가~나 과정을 반복한다.
위 과정으로 계산식3의 연산과정을 나타내보았다.
위와 같이 후위 표기식으로 변환하면 순차적으로 계산이 가능합니다.
2. 알고리즘
1) 알고리즘
- ‘(’를 만나면 스택에 푸시
- ) 피연산자는 출력
- ‘)’는 ‘(’를 만날 때 까지 팝하여 계산, ‘(’ 만나면 괄호는 버린다(팝).
- 연산자는 자신보다 낮은 연산자를 만날 때 까지 팝하고 계산, 만나면 자신을 푸시한다.
- 스택이 비었으면 푸시, 우선순위는 ( ‘(’ : 0 순위, ‘+-’ : 1순위, ‘*/’ : 2순위)
- 끝나면 스택의 모든 연산자를 팝하여 계산한다.
2) 소스
‘(’ 인 경우
- Stack.Push('('); 스택에 바로 푸시한다.
숫자인 경우
‘)’ 인 경우
연산자인 경우
입력이 끝난 경우
3. 프로그램 실행 결과
반응형