[BOJ] 1935번 후위 표기식2

풀이

후위 표기식은 스택을 이용하여 계산 가능하다는 사실을 알고 있었기에 쉽게 구현이 가능했다. 세부적인 내용은 다음과 같다.

A B C * + D E / - 이렇게 식이 존재한다.
우리는 이 식을 앞에서부터 기호를 찾아준다. 제일 앞에 있는 기호는 '*' 기호이다.
그 기호를 기준으로 왼쪽의 두 문자로 계산을 진행해준다.즉 A (B * C) 이렇게 된다.
이후 '+' 기호를 이용하여 A + ( B * C ) 를 완성해 주고, 나머지 부분도 계산하면 위 식은
A + (B \* C ) - ( D / E ) 과 같다.
중요한 부분은 앞에서 부터 시작하여 기호를 기준으로 이전의 두 원소를 계산해 준다는 것이다. 이를 스택으로 이용하여 알파뱃이면 해당하는 피연산자를 스택에 추가하고, 기호가 온다면 top에 있는 두 원소를 꺼내 계산을 진행해 주고, 다시 스택에 추가해주었다.

코드

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

void init() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
}

int main() {
	init();

	int n;
	string func;
	cin >> n >> func;

	vector<int> v(n);	// 피연산자를 저장하는 변수
	stack<double> st;	// 계산을 저장하는 stack 변수

	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	for (int i = 0; i < func.length(); i++) {
		if (isalpha(func[i])) {		
        // 만약 func[i] 번째 값이 알파뱃이라면 알파뱃에 해당하는 피연산자를 스택에 넣어준다.
			st.push(v[func[i] - 'A']);
		}
		else {		// 알파뱃이 아닌 기호가 온다면
			if (!st.empty()) {
				double temp;
				double tempA = st.top(); st.pop();		// 계산에 사용할 두 값을 추출해준다
				double tempB = st.top(); st.pop();
				// 기호에 알맞은 연산을 진행해 준 이후, 스택에 다시 넣어준다.
				if (func[i] == '+') {
					temp = tempA + tempB;
				}
				else if (func[i] == '-') {
					temp = tempB - tempA;
				}
				else if (func[i] == '*') {
					temp = tempA * tempB;
				}
				else if (func[i] == '/') {
					temp = tempB / tempA;
				}
				st.push(temp);
			}
		}
	}

	cout << fixed;
	cout.precision(2);
	cout << st.top();

	return 0;
}

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