백준 1935 - 후위 표기식 (C++)

 

 

후위 표기식이란, 연산자 앞에 있는 두 숫자에 대해 해당 연산을 진행하는 방식이라고 한다.

이렇게, 가장 앞에 놓여진 연산자를 기준으로 앞에 있는 두 숫자에 대해 우선적으로 연산을 진행하는 방식이다.

주어진 후위 표기식에 대한 계산 결과를 출력해주면 된다.

 

문제 풀이

 

연산자를 만났을 때, 앞에 있는 두 숫자에 대해 연산을 해주어야 한다.

이처럼 순서를 유지한 채로 연산을 진행할 때엔 Stack을 사용하는 것이 좋다.

 

 

이렇게 주어진 후위 표기식에서 한 번 연산을 진행하면 아래와 같은 결과가 나온다.

 

이 순서대로 다시 후위표기식의 연산을 진행해야 한다.

 

그러므로, 주어진 후위 표기식을 stack에 하나씩 삽입하다 연산자를 만나면 앞의 숫자 2개를 꺼내 연산을 한 뒤, 결과값을 다시 stack에 저장하고, 다시 후위 표기식을 하나씩 stack에 삽입하는 것을 반복하면 된다.

 

풀이 코드

int Size = 0;
std::cin >> Size;

std::string Command;
std::cin >> Command;

std::vector<int> Nums(Size);
for (int i = 0; i < Size; i++)
{
    std::cin >>	Nums[i];
}

 

Size는 후위표기식에 주어진 숫자가 몇개인지에 대한 변수이다.

Command는 후위 표기식이다.

 

Nums는 각 알파벳에 대응하는 숫자를 저장한 배열이다.

(A는 0번 인덱스, B는 1번 인덱스.....)

 

std::stack<double> Stack;

for (int i = 0; i < Command.size(); i++)
    
    if(Command[i] >= 'A' && Command[i] <= 'Z')
    {
        double CurNum = Nums[Command[i] - 'A'];
        Stack.push(CurNum);
    }
    else
    {
        double Num1 = Stack.top();
        Stack.pop();

        double Num2 = Stack.top();
        Stack.pop();

        if (Command[i] == '+')
        {
            Stack.push(Num2 + Num1);
        }
        else if (Command[i] == '-')
        {
            Stack.push(Num2 - Num1);
        }
        else if (Command[i] == '*')
        {
            Stack.push(Num2 * Num1);
        }
        else if(Command[i] == '/')
        {
            Stack.push(Num2 / Num1);
        }
    }
}

 

위의 코드를 보면, 현재 후위표기식의 요소가 A~Z라면, 해당 알파벳에 대응하는 숫자를 stack에 삽입해주었다.

만약, 연산자라면 앞의 두 숫자를 stack에서 꺼낸 뒤, 연산하여 다시 stack에 넣는 작업을 반복하고 있다. 

 

printf("%.2f", Stack.top());

return 0;

 

연산이 끝나면 stack에는 1개의 숫자만 남게 된다.

해당 숫자를 출력해주면 끝이다.

소숫점 n자리까지 출력하고 싶다면 위처럼 %.(n)f 의 형식을 사용하면 된다.

 

 

코드 전문

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

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int Size = 0;
    std::cin >> Size;

    std::string Command;
    std::cin >> Command;

    std::vector<int> Nums(Size);
    for (int i = 0; i < Size; i++)
    {
        std::cin >>	Nums[i];
    }

    std::stack<double> Stack;

    for (int i = 0; i < Command.size(); i++)
    {
        if(Command[i] >= 'A' && Command[i] <= 'Z')
        {
            double CurNum = Nums[Command[i] - 'A'];
            Stack.push(CurNum);
        }
        else
        {
            double Num1 = Stack.top();
            Stack.pop();

            double Num2 = Stack.top();
            Stack.pop();

            if (Command[i] == '+')
            {
                Stack.push(Num2 + Num1);
            }
            else if (Command[i] == '-')
            {
                Stack.push(Num2 - Num1);
            }
            else if (Command[i] == '*')
            {
                Stack.push(Num2 * Num1);
            }
            else if(Command[i] == '/')
            {
                Stack.push(Num2 / Num1);
            }
        }
    }

    printf("%.2f", Stack.top());

    return 0;
}