【Leetcode】150. Evaluate Reverse Polish Notation（栈）（算数模拟）

蔚落 2022-02-03 23:19 104阅读 0赞

Evaluate the value of an arithmetic expression in [Reverse Polish Notation][].

Valid operators are `+`, `-`, `*`, `/`. Each operand may be an integer or another expression.

**Note:**

*  Division between two integers should truncate toward zero.
 *  The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

Input: ["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

题目大意：

给出字符串，其中每个算式先给出运算的左右两个部分，再给出运算符。

解题思路：

使用栈，不难看出当遇到运算符时，我们都会找前面的两个数计算之后再丢入栈内。

class Solution {
    private:
        vector<int> nums;
        bool valid(string a){
            if((a[0]=='+'||a[0]=='-'||a[0]=='*'||a[0]=='/')&&a.length()==1) return false;
            return true;
        }
        int com_next(string s){
            int len_size = nums.size();
            int a, b;
            a = nums[len_size-2], b = nums[len_size-1];
            nums.pop_back();
            nums.pop_back();
            if(s=="+") return a+b;
            if(s=="-") return a-b;
            if(s=="*") return a*b;
            if(s=="/") return a/b;
            return 0;
        }
        int str2int(string l){
            int end_idx = 0;
            if(l[0]=='-') end_idx = 1;
            int len_size = l.length();
            int ans = 0, t=0;
            for(int i = len_size-1;i>=end_idx;i--){
                ans+=((l[i]-'0')*pow(10,t++));
            }
            return (end_idx==1)?-1*ans:ans;
        }
    public:
        int evalRPN(vector<string>& tokens) {
            if(tokens.size()==0) return 0;
            for(int i=0;i<tokens.size();i++){
                if(valid(tokens[i])){
                    nums.push_back(str2int(tokens[i]));
                }else{
                    nums.push_back(com_next(tokens[i]));
                }
            }
            return nums[0];
        }
    };

[Reverse Polish Notation]: http://en.wikipedia.org/wiki/Reverse_Polish_notation