【Leetcode】150. Evaluate Reverse Polish Notation（栈）（算数模拟）-蒲公英云

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

蔚落 2022-02-03 23:19 248阅读 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];
    }
};