首页 > 代码库 > 【Leetcode】Evaluate Reverse Polish Notation

【Leetcode】Evaluate Reverse Polish Notation

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



1st ( 9 tries )

class Solution {public:    bool isnum(string &s)    {        bool minus = false;        if(s[0] == ‘-‘)            minus = true;        if(minus)        {            if(s.length() == 1)                return false;            else            {                for(int i = 1;i < s.length();i++)                {                    if(s[i] < ‘0‘ || s[i] > ‘9‘)                        return false;                }                return true;            }        }        else        {            for(int i = 0;i < s.length();i++)            {                if(s[i] < ‘0‘ || s[i] > ‘9‘)                    return false;            }            return true;        }    }    int evalRPN(vector<string> &tokens)     {        stack<string> numst;                for(int i = 0;i < tokens.size();i++)        {            if(isnum(tokens[i]))            {                numst.push(tokens[i]);            }            else            {                int r = atoi(numst.top().c_str());                numst.pop();                int l = atoi(numst.top().c_str());                numst.pop();                int re = 0;                if(tokens[i] == "+")                {                    re = l+r;                }                if(tokens[i] == "-")                {                    re = l-r;                }                if(tokens[i] == "*")                {                    re = l*r;                }                if(tokens[i] == "/")                {                    re = l/r;                }                stringstream ss;                ss<<re;                numst.push(ss.str());            }        }        int re = atoi(numst.top().c_str());        return re;    }};

  


2nd (1 tries)
class Solution {public:    int evalRPN(vector<string> &tokens) {        stack<int> st;        for(int i = 0;i < tokens.size();i++) {            if(tokens[i] == "+") {                int right = st.top();                st.pop();                int left = st.top();                st.pop();                st.push(left+right);            }            else if(tokens[i] == "-") {                int right = st.top();                st.pop();                int left = st.top();                st.pop();                st.push(left-right);            }            else if(tokens[i] == "*") {                int right = st.top();                st.pop();                int left = st.top();                st.pop();                st.push(left*right);            }            else if(tokens[i] == "/") {                int right = st.top();                st.pop();                int left = st.top();                st.pop();                st.push(left/right);            }            else {                int number = atoi( tokens[i].c_str() );                st.push(number);            }         }         return st.top();    }};