Evaluate Reverse Polish Notation--LeetCode-蒲公英云

Evaluate Reverse Polish Notation--LeetCode

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

思路：使用栈这个数据结构，只不过需要字符串和整数整数和字符串之间的转换

#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;
int strtoi(string& s)
{
    if(s.length() == 0)
      return 0;
    int i=0,flag=1,result=0;
    if(s[0]=='-')
    {
       flag =-1;
       i++;   
    }
    if(s[0]=='+')
    {
       i++;    
    }
    for(;i<s.length();i++)
    {
        result *= 10;
        result += (s[i]-'0');                 
    }
    return result*flag;
}
string itostr(int num)
{
    int flag =1,count = num;
    if(num <0)
    {
        flag = 0;
        count = -count;   
    }
    string result;
    while(count)
    {
      result += (count%10 +'0');
      count = count/10;
    }
    if(flag == 0)
     result += '-';
    reverse(result.begin(),result.end());
    return result;   
}
int evalRPN(vector<string> &tokens) 
{
   stack<string> sk;
   int result =0,i,temp;
   string first,second;
   for(i=0;i<tokens.size();i++)
   {
       if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/")
       {
          first = sk.top();
          sk.pop();
          second =sk.top();
          sk.pop();
          if(tokens[i] == "+")
             temp = strtoi(first)+strtoi(second);
          else if(tokens[i]=="-")
             temp = strtoi(first)-strtoi(second);          
          else if(tokens[i]=="*")
             temp = strtoi(first)*strtoi(second);
          else
             temp = strtoi(second)/strtoi(first);
          first = itostr(temp);
          sk.push(first);
       } 
       else
        sk.push(tokens[i]);                       
   }
   first = sk.top();
   result = strtoi(first);
   return result;     
}
int main()
{
    string array[]={"4", "13", "5", "/", "+"};
    vector<string> tokens(array,array+sizeof(array)/sizeof(array[0]));
    cout<<evalRPN(tokens)<<endl;
    system("pause");
    return 0;
    }