Evaluate Reverse Polish Notation-阿里云开发者社区

Evaluate Reverse Polish Notation

2014-11-21 881

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /.

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

注意：一定要使用后出栈的操作数作为第一操作数，否则，对于没有对称操作的操作符会出错。

C++实现代码：

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

class Solution
{
public:
    int evalRPN(vector<string> &tokens)
    {
        stack<int> operand;
        int operand1;
        int operand2;
        if(tokens.empty())
            return 0;
        int i;
        for(i=0; i<(int)tokens.size(); i++)
        {
            if(tokens[i]=="+")
            {
                if(!operand.empty())
                {
                    operand1=operand.top();
                    operand.pop();
                }
                if(!operand.empty())
                {
                    operand2=operand.top();
                    operand.pop();
                }
                operand2+=operand1;
                operand.push(operand2);
            }
            else if(tokens[i]=="-")
            {
                if(!operand.empty())
                {
                    operand1=operand.top();
                    operand.pop();
                }
                if(!operand.empty())
                {
                    operand2=operand.top();
                    operand.pop();
                }
                operand2-=operand1;
                operand.push(operand2);
            }
            else if(tokens[i]=="*")
             {
                if(!operand.empty())
                {
                    operand1=operand.top();
                    operand.pop();
                }
                if(!operand.empty())
                {
                    operand2=operand.top();
                    operand.pop();
                }
                operand2*=operand1;
                operand.push(operand2);
            }
            else if(tokens[i]=="/")
             {
                if(!operand.empty())
                {
                    operand1=operand.top();
                    operand.pop();
                }
                if(!operand.empty())
                {
                    operand2=operand.top();
                    operand.pop();
                }
                operand2/=operand1;
                operand.push(operand2);
            }
            else
            {
                operand1=atoi(tokens[i].c_str());
                operand.push(operand1);
            }
        }
        return operand.top();
    }
};

int main()
{
    Solution s;
    vector<string> vec={"4","13","5","/","+"};
    cout<<s.evalRPN(vec)<<endl;
}

文章标签：

C++

Evaluate Reverse Polish Notation

热门文章

最新文章

相关电子书