leecode 解题总结：150. Evaluate Reverse Polish Notation

#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <stack>#include <unordered_map>#include <sstream>using namespace std;/*问题: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分析：著名的逆波兰数问题，可以用栈来解决。规则1：每次遇到数字，压入到栈中；每次遇到符号弹出栈中的两个数并利用该符号做运算，运算的结果再次压入到栈中，直到所有都遍历完，栈中只剩一个数字，就是结果。注意后取出的两个运算的数，第一个取出的放在运算符后，第二个取出的放在运算符前输入:52 1 + 3 *54 13 5 / +输出:96关键：1每次遇到数字，压入到栈中；每次遇到符号弹出栈中的两个数并利用该符号做运算，运算的结果再次压入到栈中，直到所有都遍历完，栈中只剩一个数字，就是结果。注意后取出的两个运算的数，第一个取出的放在运算符后，第二个取出的放在运算符前*/class Solution {public:    int evalRPN(vector<string>& tokens) {		if(tokens.empty())		{			return 0;		}        stack<string> datas;		int size = tokens.size();		int first = 0;		int second = 0;		int result;		unordered_map<string , bool> operators;		operators["+"] = true;		operators["-"] = true;		operators["/"] = true;		operators["*"] = true;		for(int i = 0 ; i < size ; i++)		{			first = second = 1;			//找到运算符			if(operators.find(tokens.at(i)) != operators.end())			{				//如果栈不空				if(!datas.empty())				{					//先弹出的数是第二个数					second = atoi(datas.top().c_str());					datas.pop();					if(!datas.empty())					{						first = atoi(datas.top().c_str());						datas.pop();					}					if( "+" == tokens.at(i) )					{						result = first + second;					}					else if("-" == tokens.at(i))					{						result = first - second;					}					else if("*" == tokens.at(i))					{						result = first * second;					}					else if("/" == tokens.at(i))					{						result = first / second;					}					stringstream stream;					stream << result;					datas.push(stream.str());				}			}			else			{				datas.push(tokens.at(i));			}		}		result = 0;		if(!datas.empty())		{			result = atoi(datas.top().c_str());		}		return result;    }};void print(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<string> nums;	 string value;	 int num;	 Solution solution;	 int result;	 while(cin >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 result = solution.evalRPN(nums);		 cout << result << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}