C++ ] leetCode 150 - Evaluate Reverse Polish Notation

 

 

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.

 

 

Example 1:

• Input: tokens = ["2","1","+","3","*"]
• Output: 9
• Explanation: ((2 + 1) * 3) = 9

 

 

Example 2:

• Input: tokens = ["4","13","5","/","+"]
• Output: 6
• Explanation: (4 + (13 / 5)) = 6

 

Example 3:

• Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
• Output: 22
• Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22

 

Constraints:

• 1 <= tokens.length <= 104
• tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

 

 

postfix 계산법은 예전에 정보처리기사 공부할 때 본 이후로 처음본다. 딱 stack을 위한 문제이다.

 

tokens를 순회하면서 operator가 아니면 스택에 push하고 operator라면 스택에서 가장 위에 있는 두 operands를 pop해서 연산 후 연산 결과를 다시 push하면 된다.

 

피연산자를 꺼낼때 먼저 top에 있는게 뒤에 오는 연산대상이란 점에 주의하고 마지막에는 top을 리턴하면 된다.

 

 

#include <string>
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        int n = tokens.size();
        stack<int> operands;

        for(int i = 0; i < n; i++) {   
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                int op1, op2;
                op2 = operands.top();
                operands.pop(); 
                op1 = operands.top();
                operands.pop();

                switch(tokens[i][0]) {
                    case '+':
                    operands.push(op1 + op2);
                    break;
                    case '-':
                    operands.push(op1 - op2);
                    break;
                    case '*':
                    operands.push(op1 * op2);
                    break;
                    case '/':
                    operands.push(op1 / op2);
                    break;
                }                
            }
            else {
                operands.push(stoi(tokens[i]));
            }           
        }  
        return operands.top();      
    }
};