1935 후위 표기식2

후위 표기식이란

우리가 일반적으로 사용하는 A+B 와 다르게 AB+ 처럼 연산자가 뒤로 가는 표기법

컴퓨터가 연산을 하기 쉽게 표현하는 방법임

이를 응용한 문제

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

1. 문제

---

간단 설명

후위 표현식이 주어지는데,

그 사이의 피연산자들이 알파벳으로 주어진다

이를 숫자로 치환하여 올바른 결과값을 출력하는 문제

2. 문제 분석

---

주의점

1. 후위표현식의 연산자 순서에 주의할 것 A/B와 B/A은 다르다

2. 피연산자는 A~Z 이므로 최대 26개이고, 100보다 작거나 같은 자연수이다

   즉 최대 3자리수까지 가능하다

3. 소수점 두자리수까지 출력. 결과가 자연수가 나와도 4.00과 같이 소수점 둘째자리까지 출력한다

필요변수

피연산자의 개수 N, 후위 표기식 받을 문자열 str

각 피연산자에 대응하는 값을 저장할 벡터 v

문제 해결을 위해 사용할 스택 st

그외 변수들

알고리즘

1. 각종 변수들 입력받고, 피연산자 대응 숫자를 저장해둔다
2. 표현식의 첫글자부터 스택에 넣어본다
3. 후위표현식이므로, 연산자가 나오면 스택에 넣지 않고 확인시작
    3-1. 스택에서 두개를 꺼낸다
    3-2. 가장 위에있던 수를 B, 그 다음에 나오는 수를 A라고 함 (연산자 순서 중요함)
    3-3. A와 B를 들고있던 연산자를 이용해 수행한 뒤
    3-4. 결과값을 스택에 다시 넣는다
4. 3을 표현식의 끝까지 수행한다
5. 스택에 저장되어있는 결과값인 st.top()을 출력한다.

처음 시도한 알고리즘은

표현식을 처리하기전에 미리 숫자로 치환하고 스택에 넣는 방식으로 했으나

피연산자가 두자리 이상이라면 문제가 발생하였음

이를 해결하려고 두번째 시도한 알고리즘은

스택을 string을 저장하는 식으로 했으나 형 변환 지옥을 맛봄

char형 A를 string으로 변환해서 스택에 넣었다가 다시 빼서

이에 맞는 피연산자 숫자를 찾기위해 정수형으로 변환했다가 난리를 치다가 포기

3. 소스코드

---

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

using namespace std;

int main() {
    // 1. 입력받기
	freopen_s(new FILE*, "input.txt", "r", stdin);
	int N;
	cin >> N;
	vector<int> v(N);

	string str;
	cin >> str;

	// 피연산자에 대응하는 숫자를 저장
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}

	// 나눗셈을 위해 double로 생성
	stack<double> st;

    // 2. 표현식의 첫글자부터 스택에 넣어보기
	for (int i = 0; i < str.size(); i++) {
        // 알파벳이라면 그냥 넣는다
		if (str[i] >= 'A' && str[i] <= 'Z') {
			st.push(v[str[i] - 'A']);
		}
        // 3. 연산자가 나오면 스택에 넣지 않고 연산 수행
		else {
			double b = st.top(); st.pop(); // 순서에 주의할 것
			double a = st.top(); st.pop();

			if (str[i] == '+') { a = a + b; }
			else if (str[i] == '-') { a = a - b; }
			else if (str[i] == '*') { a = a * b; }
			else if (str[i] == '/') { a = a / b; }

            // 3-4. 결과값을 스택에 다시 넣는다
			st.push(a);
		}
	}

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

	return 0;
}