[LeetCode] Evaluate Reverse Polish Notation stack 栈

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

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

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Hide Tags

Stack

题目是用 stack 维护一个公式的进出，判断方法还可以，开始忘记数可能为负，后面改进了。

#include <stack>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        int n = tokens.size();
        stack<int > tmp;
        for(int i=0;i<n;i++){
            if(tokens[i][0]>='0'&&tokens[i][0]<='9'){
                tmp.push( helpFun(tokens[i]) );
                continue;
            }
            if(tokens[i][0]=='-'&&tokens[i][1]!='\0'){
                tmp.push( helpFun( tokens[i]));
                continue;
            }
            int rgt = tmp.top();
            tmp.pop();
            int lft = tmp.top();
            tmp.pop();
            switch (tokens[i][0]){
            case '+':
                tmp.push( lft + rgt );
                break;
            case '-':
                tmp.push(lft - rgt);
                break;
            case '*':
                tmp.push(lft * rgt);
                break;
            case '/':
                tmp.push(lft / rgt);
                break;
            }
        }
        return tmp.top();
    }

    int helpFun(string str)
    {
        int sum = 0,i = 0;
        if (str[0]=='-')
            i = 1;
        for(;i<str.length();i++)
            sum = sum*10+str[i]-'0';
        return str[0]=='-'?-sum:sum;
    }
};

int main()
{
    vector<string> tokens{"3","-4","+"};
    Solution sol;
    cout<<sol.evalRPN(tokens)<<endl;
//    for(int i=0;i<tokens.size();i++)
//        cout<<tokens[i]<<endl;
    return 0;
}

[LeetCode] Evaluate Reverse Polish Notation stack 栈

推荐阅读