[BOJ/백준 1935][C++] 후위 표기식2

문제

https://gyong0117.tistory.com/

문제 내용

후위 표기식과 피연산자들에 해당하는 값들이 주어졌을 때 식을 계산하여 소수점 둘째 자리까지 출력하는 문제이다.

 

1. 중위 표기식이란?

중위 표기법은 우리가 흔히 사용하는 표기법으로 피연산자 사이에 연산자를 두는 방식이다.
3*5, 4+7, 5/2 등이 중위 표기식에 해당한다.

2. 후위 표기식이란?

후위 표기법은 연산자를 피연산자 뒤에 놓는 방법이다.
위의 중위 표기식을 후위 표기식으로 바꾸면 35*, 47+, 52/ 과 같은 형태로 적을 수 있다.

 

문제 풀이

후위 표기식을 계산하기 위해는 stack을 사용하는 것이 좋다.
더불어, 식의 결과와 중간 결과가 -20억보다 크거나 같고, 20억보다 작거나 같다고 했기 때문에 double 자료형을 써야 한다. (float을 쓰면 틀린다.)

후위 표기식을 string으로 입력받고 앞에서부터 차례로 한 글자씩 확인하며 처리한다.

해당 문자가 알파벳이라면 num배열에서 해당 알파벳에 대응하는 숫자를 불러와서 stack에 push 한다.
이때 num배열의 인덱스를 str[i]-'A' 과 같은 방식으로 적었는데, 이는 num배열에 숫자를 저장할 때, A에 해당하는 문자부터 차례로 저장되기 때문이다.
str[i]가 알파벳 A라면 'A'-'A'로 0이 나오기 때문에 num[0]에 접근할 수 있다.
str[i]가 알파벳 B라면 num[1]에 접근이 가능하다.

해당 문자가 기호라면 스택에서 가장 위에 두 숫자를 꺼내서 계산을 진행하고 결과를 다시 stack에 push 한다.
이때 먼저 꺼낸 숫자가 중위 표기식을 기준으로 했을 때 연산자 뒤에 오는 피연산자이다.

후위 표기식의 계산이 끝나면 stack에는 하나의 원소만 남게 된다.
이를 소수점 두 번째 자리까지 출력하면 문제를 해결할 수 있다.

 

코드

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

double calculate(char ch,double first,double second) {
	if (ch == '+') return first + second;
	if (ch == '-') return first - second;
	if (ch == '*') return first * second;
	if (ch == '/') return first / second;
}

int main() {
	//입력
	int n;
	string str;
	cin >> n >> str;

	vector<int>num(n);
	for (int i = 0; i < n; i++)cin >> num[i];
	
    	//문제 해결
	double first,second;
	stack<double>s;

	for (int i = 0; i < str.size(); i++) {
		if ('A'<=str[i] && str[i]<='Z') {//해당문자가 알파벳일때
			s.push((double)num[str[i]-'A']); //num배열에서 숫자 가져와서 스택에 추가
		}
		else {//해당문자가 기호일때
			second = s.top(); s.pop();
			first = s.top(); s.pop();
			s.push(calculate(str[i], first, second));
		}
	}
    
    	//결과 출력
	double result = s.top();
	printf("%.2f\n", result);
}

 

문제 코드 설명

1) calculate(char ch, double first, double second) 함수

연산자와 피연산자를 입력받아 계산을 진행하고 결과를 반환하는 함수이다.

 

2) 문제 해결

입력받은 후위 표기식(코드에서 str)을 앞에서부터 한 글자씩 읽으며 처리하기 위해 for문을 사용했다.
지금 처리하는 문자가 알파벳인지 기호인지를 구분하기 위해 조건문을 사용했다.

알파벳이라면 대응되는 숫자를 stack에 push()한다.

기호라면 stack에서 top()을 통해 가장 위의 값을 받아오고, pop()을 통해 그 값을 stack에서 삭제하는 과정을 두 번 진행하여 가장 위의 숫자 두 개를 받아온다.
그리고 계산을 진행한 결괏값을 다시 stack에 push()하면 된다.

3) 결과 출력

후위 표기식의 계산이 끝나면 stack에는 한 가지 요소만 남아있다.
이를 result 변수에 집어넣고, printf("%.2f\n")를 통해 소수점이 두 자리까지만 출력되도록 했다.