[LeetCode] 150. Evaluate Reverse Polish Notation

https://leetcode.com/problems/evaluate-reverse-polish-notation/description/?envType=daily-question&envId=2024-01-30

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - Evaluate Reverse Polish Notation

문제 유형 : 스택, 후위표기식

문제 난이도 : Medium

 

문제

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

• The valid operators are '+', '-', '*', and '/'.
• Each operand may be an integer or another expression.
• The division between two integers always truncates toward zero.
• There will not be any division by zero.
• The input represents a valid arithmetic expression in a reverse polish notation.
• The answer and all the intermediate calculations can be represented in a 32-bit integer.

 

당신은 후위표기식으로 tokens라는 문자열을 받는다.

수식 연산값을 반환하시오.

 

• 연산자는 '+', '-', '*', '/'중에 있다.
• 각 오퍼랜드는 정수이거나 다른 수식이다.
• 나눗셈에서 0아래로는 자른다.
• division by zero의 케이스는 제외한다.
• 식은 유효하게 주어진다.
• 32비트정수 내로 계산되도록 제공된다.

 

풀이

오퍼랜드를 저장하기 위한 스택을 생성한다.

각 토큰을 읽는다.

토큰이 연산자라면, 스택에서 오퍼랜드를 두 개 꺼내서 연산한 뒤, 다시 스택에 넣는다.

이때, 늦게 꺼낸 오퍼랜드를 b, 먼저 꺼낸 오퍼랜드를 a라고 했을 때, b-a와같이 연산해야 한다.

피연산자라면, 스택에 넣는다.

유효하게 식이 주어지므로, 각 토큰을 한 번씩 읽으면, 스택에는 숫자가 하나 남는데, 그 숫자가 연산의 결과이다.

 

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int op(int a, int b, char opt) {
        switch (opt) {
            case '+':
                return b+a;
            case '-':
                return b-a;
            case '*':
                return b*a;
            case '/':
                return b/a;
        }
        return 0;
    }

    int evalRPN(vector<string>& tokens) {
        stack<int> st;

        for(const auto &token : tokens) {
            if(!isdigit(token[0]) && token.size() == 1) {
                int operandA = st.top();
                st.pop();
                int operandB = st.top();
                st.pop();

                st.push(op(operandA, operandB, token[0]));
            } else {
                st.push(stoi(token));
            }
        }

        return st.top();
    }
};