[C/C++] 코드업(codeup) 3127번 수식 계산 1

▽문제 바로가기

https://codeup.kr/problem.php?id=3127

수식 계산 1

---

입력

후위 표기법으로 된 식이 입력된다.

주어지는 식은 자연수와 덧셈, 뺄셈, 곱셈만으로 이루어져 있으며, 각 자연수와 연산자 사이는 띄어 쓰기 되어 있다.

전체 식의 길이는 공백 문자 포함 200자 이하이다.

식에 포함된 자연수 및 식의 계산 결과는 230을 넘지 않는다.

 

출력

식의 계산결과를 출력한다.

 

문제 풀이

 

이 문제를 풀려면 후위 표기법을 먼저 이해해야 합니다.

 

우리는 평소 중위 표기법을 사용합니다. 계산할 두 숫자 사이에 연산자를 넣습니다. 2와 3을 더하고 싶으면 2 + 3으로 표현합니다.

반면, 후위 표기법은 숫자를 먼저 표기하는 방식입니다. 2와 3을 더하고 싶으면 2 3 + 으로 표현합니다.

 

입력 예시로 1 2 3 * + 4 5 - 6 * + 의 계산 과정을 추적해봅시다.

 

1입력 : 1

2입력 : 1 2

3입력 : 1 2 3

*입력 : 1 (2 * 3) = 1 6

+입력 : 1 + 6 = 7

4입력 : 7 4

5입력 : 7 4 5

-입력 : 7 (4-5) = 7 -1

6입력 : 7 -1 6

*입력 : 7 (-1 * 6) = 7 -6

+입력 : 7 + (-6) = 1

 

연산자가 입력되면 숫자들 중 가장 뒤에 입력된 숫자 두 개가 연산자와 계산합니다. 가장 늦게 들어오는 것이 가장 먼저 나오는 스택(stack) 구조임을 알 수 있습니다.

 

#include <stdio.h>

using namespace std;

int main(){
	
	char arr[201];
	
	gets(arr);
	
	int stack[101];
	int top = -1;
	
	for(int i=0;arr[i]!='\0';i++){
		//숫자 처리
		if(arr[i]>=48&&arr[i]<=57){
			int num = 0;
			//숫자가 일의자리 이상일 경우도 있으므로
			for(;;i++){
				if(arr[i]<48||arr[i]>57) break;
				num = num*10 + (arr[i] - 48);
			}
			top++;
			stack[top] = num;
		}
		//연산자 처리
		else{
			if(arr[i]=='+'){
				stack[top-1] = stack[top-1] + stack[top];
				top--;
			}
			else if(arr[i]=='-'){
				stack[top-1] = stack[top-1] - stack[top];
				top--;
			}
			else if(arr[i]=='*'){
				stack[top-1] = stack[top-1] * stack[top];
				top--;
			}
		}
	}
	
	printf("%d", stack[0]);
	
	return 0;
}