首页 > 其他 > 详细

leetcode - [2]Evaluate Reverse Polish Notation

时间:2014-09-20 01:07:16      阅读:282      评论:0      收藏:0      [点我收藏+]

Evaluate Reverse Polish Notation

 Total Accepted: 24595 Total Submissions: 123794My Submissions

 

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

 

 

Have you been asked this question in an interview? 

思路:栈的简单应用

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <cstdlib>

using namespace std;


class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        stack<int> s;
        string str;
        int a, b;

        for (int i = 0; i < tokens.size(); i++) {
            str = tokens[i];
            if (str == "+" || str == "-" || str == "*" || 
                a = s.top(); s.pop();
                b = s.top(); s.pop();
                switch(str[0]) {
                    case +: s.push(b+a); break;
                    case -: s.push(b-a); break;
                    case *: s.push(b*a); break;
                    case /: s.push(b/a); break;
                    }
            }
            else {
                s.push(atoi(str.c_str()));
            }
        }
        a = s.top();s.pop();
        return a;
    }
};


int main(int argc, char *argv[]) {
    Solution* solution = new Solution();
    vector<string> tokens;
    tokens.push_back("2");
    tokens.push_back("1");
    tokens.push_back("+");
    tokens.push_back("3");
    tokens.push_back("*");

    cout << solution->evalRPN(tokens) << endl;

    vector<string> tokens2;
    tokens2.push_back("4");
    tokens2.push_back("13");
    tokens2.push_back("5");
    tokens2.push_back("/");
    tokens2.push_back("+");
    cout << solution->evalRPN(tokens2) << endl;
    return 0;
}

 

leetcode - [2]Evaluate Reverse Polish Notation

原文:http://www.cnblogs.com/zhuangzebo/p/3982737.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!