[ 백준 1935 ] 후위 표기식2 (C++)

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

1935번: 후위 표기식2

 

후위 표기식의 계산법을 알기만 하면 간단하게 풀 수 있는 문제다. 하지만 나는 원리를 잘 몰랐기 때문에 꽤나 고민했다. 정답을 보고 푼 것은 아니지만 알고리즘에 대한 선행 학습을 하고난 뒤에 풀어서 정답을 보고 푼 것 같은 느낌이다. 후위 표기식을 계산하기 위해서는 스택이 필요하다. 그리고 아래 두 가지 규칙만 지켜주면 된다.

​

1. 피연산자면 스택에 push

2. 연산자면 스택에서 두 개 pop해서 연산 후 결과값 push

​

아주 간단하다. 123*+45/-를 계산하는 예시를 살펴보자. 단, 스택에서 꺼낼 때 계산 순서가 (아래쪽) + (위쪽) 임을 주의하자.

 

위 두 가지 규칙 그대로 코드로 구현하면 아래와 같다. 문제에서는 대문자 알파벳을 숫자로 치환해주는 과정이 있음에 유의하자.

 

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

using namespace std;

int main() {
	int N;
	double f1, f2, nums[26];
	string input;

	cin >> N >> input;
	for (int i = 0; i < N; i++) 
		cin >> nums[i];
	

	// 1. 피연산자는 치환 후 스택에 push
	// 2. 연산자 만나면 두 개 pop해서 연산
	stack<double> s;

	for (int i = 0; i < input.size(); i++) {
		if (input[i] >= 'A' && input[i] <= 'Z')
			// 피연산자면 치환 후 스택에 push
			s.push(nums[input[i] - 'A']);
		else {
			// 연산자 만나면 두 개 pop 해서 연산
			f1 = s.top();
			s.pop();
			f2 = s.top();
			s.pop();
			if (input[i] == '+') s.push(f2 + f1);
			else if (input[i] == '-') s.push(f2 - f1);
			else if (input[i] == '*') s.push(f2 * f1);
			else if (input[i] == '/') s.push(f2 / f1);
		}
	}

	cout << fixed;
	cout.precision(2);
	cout << s.top() << endl;
	s.pop();

	return 0;
}