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

⭐️난이도

Silver 3

---

⭐️문제

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

후위 표기식과 각 피연산자에 대응하는 값이 주어졌을 때, 해당 식을 계산한 결과를 출력하면 되는 문제이다!

1935번: 후위 표기식2

---

⭐️ 내 풀이 &  Code

후위표기식은 대학 수업 자료구조 시간에 배운적이 있어서 그렇게 어렵진 않았다.

 

📌내가 생각한 이 문제에서의 처리 포인트

    ① 입력에서 주어지는 피 연산자에 해당하는 값을 어떻게 매핑할 것인가?

    ② Stack을 이용해서 후위표기식을 어떻게 처리할 것인가?

 

📌 ①번에 대한 방법

• int형 배열 passive을 선언하여 각 피연산자(int)의 값을 저장한다.

  입력 받을 때에는 A부터 순서대로 들어오기 때문에 for문을 통해 값을 저장!

• 후위 표기식을 검사하다가 피연산자(char형)을 만나면 passive[str[i]-'A']를 통해 접근한다.

 

📌 ②번에 대한 방법

• string으로 후위표기식 전체를 입력 받아서 for문을 통해 한 글자씩 검사한다.

• 검사 도중 연산자를 만나면 stack에서 두 개의 값을 pop하여 연산자에 해당하는 연산을 하고 다시 stack에 push

• 검사 도중 피연산자를 만나면 passive[str[i]-'A']를 통해 접근 -> stack에 push

 

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

#define MAX 26 + 1
#define INF 100000000
using namespace std;

int n, passive[MAX]; // 피연산자의 개수, 피연산자에 대응하는 값을 저장하는 변수
string str; // 후위표기식을 입력받을 string
stack<double> stk; // 스택에는 실제 값만 넣는다

void input(){
    scanf("%d", &n);
    cin >> str;
    for(int i = 0; i < n; i++){
        // A:0, B:1, C:2 ...
        scanf("%d", &passive[i]);
    }
}

double operate(char tmp, double n1, double n2){
    if(tmp == '+')  return n1 + n2;
    else if(tmp == '-') return n1 - n2;
    else if(tmp == '/') return n1 / n2;
    else if(tmp == '*') return n1 * n2;
}

void postfix(){
    for(int i = 0; i < str.length(); i++){
        // 연산자가 주어졌을 때
        if(str[i] == '+' || str[i] == '-' || str[i] == '/' || str[i] == '*'){
            double n2 = stk.top();
            stk.pop();
            double n1 = stk.top();
            stk.pop();
            double result = operate(str[i], n1, n2);
            stk.push(result);
        }
        // 피연산자가 주어졌을 때
        else{
            // A:0, B:1, C:2 ...
            stk.push(passive[str[i] - 'A']);
        }
    }
}

int main(void) {

    input();
    postfix();
    printf("%.2f", stk.top());


    return 0;
}

1935.jpg

0.91MB