[SWEA 1224] 계산기3 C++

 

SW Expert Academy

 

 

문제풀이

 

문자열로 이루어진 계산식이 주어질 때, 계산식을 후위 표기식으로 바꾸어 계산하는 문제다.

 

"3+(4+5)*6+7"라는 문자열을 후위 표기식으로 바꾸는 과정은 어떻게 될까?

 

1. 입력 받은 계산식에서 토큰을 읽는다
2. 토큰이 피연산자, 즉 숫자면 토큰을 출력한다
3. 토큰이 연산자(괄호 포함)일 경우
   스택이 비었거나 top보다 우선순위가 높으면 스택에 push
   우선순위가 높지 않으면 연산자의 우선순위가 토큰의 우선순위보다 작을때까지 스택에서 pop한 후 토큰의 연산자를 push한다
4. 토큰이 오른쪽 괄호 ')'일 경우
   스택 top에 왼쪽 괄호 '('가 올 때까지 pop 연산을 수행하면서 pop한 연산자를 출력한다
   왼쪽 괄호를 만나면 pop만 하고 출력하지 않는다
5. 계산식에 더 읽을 것이 없다면 중지, 더 읽을 것이 있다면 1부터 반복한다
6. 스택에 남아 있는 연산자를 모두 pop하여 출력

 

위 과정을 따라하면 "3+(4+5)*6+7" 문자열의 후위 표기식인 "345+6*+7+"를 얻을 수 있다.

 

 

본 문제에서는 후위 표기식으로 바꾸어 계산하라고 했지만 후위 표기식으로 바꾸는 과정에서 연산을 바로 해주었다.

문자열 계산식을 구성하는 연산자는 +, * 두 종류이기 때문에 *, + 순으로 우선순위가 높다.

우선순위가 같은 경우에도 pop을 해주어야 정확한 후위 표기식을 얻을 수 있다.

 

이번에는 그림으로 한 번 살펴보자!

 

num은 숫자를 저장한 스택, ops는 연산자를 저장한 스택이다.

 

여기까지는 쭉쭉 넣어주면 된다

 

토큰이 닫는 괄호 ')'이니까 '('를 만날 때까지 pop해서 계산을 해주고 그 계산결과를 num에 다시 넣는 과정을 반복한다.

'('를 만났으면 연산을 종료하고 '('를 pop한다.

 

이번에는 토큰이 +인데 스택의 top이 *이다. 

*의 우선순위가 더 높기 때문에 pop해서 계산을 해준다. 

그 다음 top은 +로 토큰과 우선순위가 같다.

top의 우선순위가 낮아야 하니까 또 pop해서 계산을 해준다.

더 이상 남은 연산자가 없으므로 +를 push하고 다음 토큰으로 넘어간다.

 

마지막 토큰인 7까지 다 읽었기 때문에 스택에 남은 연산을 마무리 하면 64를 얻을 수 있다!

 

 

C++ 코드