Leetcode 150 Evaluate Reverse Polish Notation

triplebee

发布于 2018-01-12 14:50:56

6330

发布于 2018-01-12 14:50:56

文章被收录于专栏：计算机视觉与深度学习基础计算机视觉与深度学习基础

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

逆波兰表达式，栈的应用

注意减和除的两个数哪个在前，哪个在后

这题的数据不够卡，如果最后结果是int，但是中间也可以溢出啊，写的时候突然想到，懒得改就浪交了，居然过了。

class Solution {
public:
    int toint(string s)
    {
        int res = 0,i = 0;
        if(s[0] == '-') i = 1;
        for(; i < s.size(); i++)
        {
            res *=10;
            res += s[i]-'0';
        }
        return s[0] == '-' ? -res : res;
    }
    int evalRPN(vector<string>& tokens) 
    {
        stack<int> s;
        for(int i = 0; i < tokens.size(); i++)
        {
            int a, b;
            if(tokens[i] == "+")
                a = s.top(), s.pop(), b = s.top(), s.pop(), s.push(a+b);
            else if(tokens[i] == "-")
                a = s.top(), s.pop(), b = s.top(), s.pop(), s.push(b-a);
            else if(tokens[i] == "*")
                a = s.top(), s.pop(), b = s.top(), s.pop(), s.push(a*b);
            else if(tokens[i] == "/")
                a = s.top(),s.pop(), b = s.top(), s.pop(), s.push(b/a);
            else
                s.push(toint(tokens[i]));
        }
        return s.top();
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2016-12-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除

each