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

🔗알고리즘 문제

지금까지는 문자가 알파벳인지 판단하는 로직을 아스키코드를 이용하여 작성하였는데 이 문제를 풀면서 isalpha라는 편리한 함수가 있다는 것을 알게 되었다. stack 자료구조에 대해서 더욱 공부할 수 있는 문제였다.

문제 분석

이 문제는 후위표기식으로 이루어진 식이 주어졌을 때 해당 식의 결과가 무엇인지 출력하는 문제이다.

후위표기식은 우리가 평소 쓰는 계산식과는 다르게 연산자가 중간이 아닌 뒤에 오는 것을 말한다. 앞에서부터 순서대로 데이터를 읽는 컴퓨터의 특성 상 컴퓨터가 계산할 때 편리한 계산식이라고 한다.

EX)

중위 표기식 => A * B

후위 표기식 => AB*

발상

후위 표기식은 앞에서 부터 순서대로 데이터를 읽는 컴퓨터한테 유리한 계산식이다. 라는 곳에서 힌트를 얻을 수 있었다.

Stack 자료구조를 사용하여 앞에서부터 계산식을 진행하며 마치 컴퓨터처럼 계산식을 진행하면 되겠다고 생각하였다.

알고리즘 설계

1. 입력받은 후위 표기식을 for문을 통해 반복한다.
2. 해당 index의 값이 계산식 ( +, -, *, / ) 이라면 스택에 있는 값들을 계산식대로 계산한다.
   해당 index의 값이 숫자라면 스택에 값을 추가시켜준다.
3. 계산 된 값을 출력한다.

코드

#include<iostream>
#include<stack>

using namespace std;

int main(){
    int count;
    string input;

    cin >> count; //피연산자 수
    cin >> input;

    double* nums = new double[count];
    stack<double> stack;

    for(int i = 0; i < count; i++) //피연산자 값 입력
        cin >> nums[i];

    for(int i = 0; i < input.length(); i++){
        if(isalpha(input[i])){ // is Alpha? A = 1, a = 2, 1,2 = 0
            stack.push(nums[input[i] - 'A']);
        }
        else{
            double temp = stack.top();
            stack.pop();

            switch (input[i])
            {
                case '+':
                    stack.top() = stack.top() + temp;
                    break;
                case '-':
                    stack.top() = stack.top() - temp;
                    break;
                case '*':
                    stack.top() = stack.top() * temp;
                    break;
                case '/':
                    stack.top() = stack.top() / temp;
                    break;
            }
        }
    }

    cout << fixed;
    cout.precision(2);
    cout << stack.top();
}