#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分析：著名的逆波蘭數(shù)問題，可以用棧來解決。規(guī)則1：每次遇到數(shù)字，壓入到棧中；每次遇到符號(hào)彈出棧中的兩個(gè)數(shù)并利用該符號(hào)做運(yùn)算，運(yùn)算的結(jié)果再次壓入到棧中，直到所有都遍歷完，棧中只剩一個(gè)數(shù)字，就是結(jié)果。注意后取出的兩個(gè)運(yùn)算的數(shù)，第一個(gè)取出的放在運(yùn)算符后，第二個(gè)取出的放在運(yùn)算符前輸入:52 1 + 3 *54 13 5 / +輸出:96關(guān)鍵：1每次遇到數(shù)字，壓入到棧中；每次遇到符號(hào)彈出棧中的兩個(gè)數(shù)并利用該符號(hào)做運(yùn)算，運(yùn)算的結(jié)果再次壓入到棧中，直到所有都遍歷完，棧中只剩一個(gè)數(shù)字，就是結(jié)果。注意后取出的兩個(gè)運(yùn)算的數(shù)，第一個(gè)取出的放在運(yùn)算符后，第二個(gè)取出的放在運(yùn)算符前*/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;			//找到運(yùn)算符			if(operators.find(tokens.at(i)) != operators.end())			{				//如果棧不空				if(!datas.empty())				{					//先彈出的數(shù)是第二個(gè)數(shù)					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;}