[C++] 백준 1935번: 후위 표기식2

https://www.acmicpc.net/problem/1935

1935번: 후위 표기식2

1. 문제

 후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오.

2. 입력

 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. 3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C ...이 주어진다, 그리고 피연산자에 대응 하는 값은 100보다 작거나 같은 자연수이다.
 후위 표기식을 앞에서부터 계산했을 때, 식의 결과와 중간 결과가 -20억보다 크거나 같고, 20억보다 작거나 같은 입력만 주어진다.

3. 출력

 계산 결과를 소숫점 둘째 자리까지 출력한다.

4. C++ 코드

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	string s;
	cin >> n >> s;
	double arr[26] = { 0, };
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	stack<double> stack;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] >= 'A' && s[i] <= 'Z') {
			stack.push(arr[s[i] - 'A']);
		}
		else if (!stack.empty()) {
			double tmp = stack.top();
			stack.pop();
			if (s[i] == '+') {
				tmp = stack.top() + tmp;
			}
			else if (s[i] == '-') {
				tmp = stack.top() - tmp;
			}
			else if (s[i] == '*') {
				tmp = stack.top() * tmp;
			}
			else if (s[i] == '/') {
				tmp = stack.top() / tmp;
			}
			stack.pop();
			stack.push(tmp);
		}
	}
	cout << fixed;
	cout.precision(2);
	cout << stack.top() << "\n";

	return 0;
}

5. 문제 풀이

 후위 표기법은 연산자를 피연산자(연산 대상)의 뒤에 쓰는 연산 표기법이다. 컴퓨터가 스택 메모리를 활용하여 계산할 수 있으므로 계산 속도가 빠른편에 속한다. 연산자(+, -, *, /)를 만날 때까지 피연산자를 스택에 저장한 후 연산자가 나오면 스택에서 꺼낸 후 계산하여 스택에 다시 저장하는 방식으로 구현하였다. 스택을 이용하여 후위 표기법으로된 식을 연산할 때 주의할 점은, 최상위 스택 아래의 값 첫 번째 피연산자, 최상위 스택의 값이 두 번째 피연산자로 하여 연산을 해야한다. 이를 고려하여 연산하기 전, 최상위 스택의 값을 tmp라는 변수에 저장하여 연산을 한 후 최상위 스택에 저장하였다.
 소수점 연산을 해야하므로 스택의 자료형은 double로 설정하였고, 소수점 둘째 자리까지 출력을 하기 위해서 cout << fixed;와 cout.precision(2);을 사용하였다.