[LeetCode]Evaluate Reverse Polish Notation(逆波兰式的计算)

原题链接：http://oj.leetcode.com/problems/evaluate-reverse-polish-notation/

题目描述：

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

题解：

　　所谓逆波兰式，即操作符位于操作数之后的表示法，我们常见的表示“三加四”都是表示成“3+4”，这是一种中缀表达式，换成逆波兰式，就应该表示成3 4 +，因此逆波兰式也称“后缀表达式”，具体的关于逆波兰式、中缀表达式、波兰式(即前缀表达式)，参见维基百科。

　　很显然，具体操作符最近的两个数便是与这个操作符对应的操作数，用栈来实现是最直观的，这道题一道比较基础的栈的应用题，详情见代码：

#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <iostream>
#include <stack>
using namespace std;

int evalRPN(vector<string> &tokens)
{
     vector<string>::iterator iter;
    stack<int> res;
    int a,b;
    for (iter=tokens.begin();iter!=tokens.end();iter++)  
    {  
        if(*iter=="+" || *iter=="-" || *iter=="*" || *iter=="/")
        {
            b = res.top();
            res.pop();
            a = res.top();
            res.pop();
            if(*iter=="+")
            {
                res.push(a+b);
            }else if(*iter=="-")
            {
                res.push(a-b);
            }else if(*iter=="*")
            {
                res.push(a*b);
            }else if(*iter=="/")
            {
                 res.push(a/b);  
            }
        }
        else
        {
            res.push(atoi((*iter).data()));
        }
    }
    return res.top();        
}
    
int main()
{
     freopen("in.in","r",stdin);
     freopen("out.out","w",stdout);
     
     vector<string> tokens;
     
     string t;
    while(!cin.eof())
    {
        cin>>t;
        tokens.push_back(t);
    }
    
    printf("%d
",evalRPN(tokens));
    return 0;    
}