티스토리 뷰

저번 포스팅에서는 사칙연산 계산기 프로그램을 만들기 위한 중위 표기식을 후위 표기법을 이용해 수식을 표현하는 방법을 알아보았다.

[Stack]사칙연산 계산기 구현(1) - 후위 표기법


이제 후위 표기 수식을 계산하기만 하면 된다.

후위 표기식을 계산하기 위해선 후위 표기 방법과 같이 자료구조 스택을 사용한다.


후위 표기식의 계산 방법은 어떻게 할까?

쉬운 계산식부터 알아보자.


중위 표기식 A + B를 후위 표기식으로 나타내면 A B + 와 같다.

먼저 풀어보면 피연산자 A와 B는 스택에 넣은 후 , 연산자 +를 만나면 스택에서 pop을 수행해 피연산자 2개, A와 B를 꺼내어 각각 변수에 담은 뒤 + 연산을 계산하고 계산된 결과 값을 다시 스택에 넣는다. 

수식이 끝났다면 스택에는 하나의 값이 저장되어있을 텐데(올바른 수식이였다면) 그것이 수식의 최종 결과가 된다.


여기서 주의해야할 점은 스택은 후입선출, Last-in First-out이므로 위와같이 A 와 B를 차례대로 스택에 넣었다면, B와 A 순서대로 pop이 될 것이다. 여기서 첫번째로 나왔다고 B + A 이렇게 그냥 나온 순서대로 수식을 계산하게 되면 덧셈이나 곱셈은 상관 없지만 뺄셈과 나눗셈에는 틀린 결과 값이 나오게 된다. 때문에 계산할 때 피연산자들의 위치를 잘 맞춰줘야한다.


후위 표기식의 계산 알고리즘을 설계하면 다음과 같다.

1. 피연산자면 스택에 push한다.


2. 연산자를 만나면 pop을 두번하고 각각 값을 저장한 후, 연산자에 맞는 계산을 한다.


3. 계산을 한 뒤, 결과 값은 다시 스택에 넣는다. 이 과정을 수식이 끝날 때 까지 반복한다.


4. 수식이 끝났다면 스택에 마지막 남은 값이 결과 값이 된다.



실제 식을 사용해 후위 표기식을 계산해보자.


중위 표기식 2 * ( 4 + 5 ) -> 후위 표기식 2 4 5 + *




1. 2는 피연산자이므로 스택에 push한다.


2. 4는 피연산자이므로 스택에 push한다.


3. 5는 피연산자이므로 스택에 push한다.


4. +는 연산자. 스택에서 pop()을 2번 수행해 각각 값을 변수에 담고 더한다. 이후 스택에 결과 값을 push한다. (위 계산식에서 5+4라고 했는데 실제론 4+5로 수행해야함) 


5. *는 연산자. 스택에서 pop()을 2번 수행해 각각 값을 변수에 담고 곱한다. 이후 스택에 결과값을 push한다.(4번과 마찬가지로 2*9로 수행해야함)


6. 수식이 끝났으므로 스택에 마지막 남은 값을 pop한다. 그 값이 최종 결과 값이다.


후위 표기식 계산 원리가 이해가 갔다면 이제 실제 코드도 구현할 수 있을 것이다! 


'DataStructure' 카테고리의 다른 글

[Stack]사칙연산 계산기 구현(1) - 후위 표기법  (13) 2018.10.07
댓글