题目：Evaluate Reverse Polish Notation

给出一个加减乘除的逆波兰式，求出它的结果；

什么是逆波兰式？

简单来说，逆波兰式就是表达式的后缀表示形式；

例如下面两个式子：

["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9

["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

它的通常形式是后面的((2 + 1) * 3)或(4 + (13 / 5))形式；

而将它转变为后缀表示形式后，直观上看就是，加减乘除的运算符放到了数字的后面；

因为上面的四种运算符都是二元运算符，即需要两个数据元；所以它表示将在它前面与它最靠近的两个数使用该运算符运算。

因此第一个式子中"+"前面是2和1，就是2+1；"/"前面是13和5，就是13/5；

有逆波兰式就有波兰式，很容易理解，波兰式就是运算表达式的前缀表示形式；我们常见的运算表达式的形式实际上是它的中缀表达式；这和二叉树的前序遍历，中序遍历，后序遍历就全部对应起来了。

 

树的前序、中序、后序遍历在树的遍历中详细讲到，这里就不多说前缀、中缀、后缀的问题，这里直接针对问题俩说明解法。

上面的逆波兰式的解法就可以用栈来实现；

过程如下：

1.遍历表达式字符串，循环退出条件是到达串尾；

2.如果当前字符是数字，则入栈并进入循环；

3.如果当前字符是运算符，因为都是二元运算符，所以从栈顶一次取出两个数字，如果栈内元素不够，则表达式有误；//因为表达式中没有括号等其他符号，否则还要考虑其他符号的问题。

4.将两个数字按照当前运算符运算，并将结果压栈；注意运算的两个数字已从栈中删除；

5，从表达式字符串中取出下一个字符，重复上面2-3的步骤；

6.最后表达式遍历完后，栈中应该只有一个结果，其他情况都表示表达式有误；取出该结果返回。

注意：数字可能是负数，此时判断是否是数字时，要区分一下这个特殊情况。

int LeetCode::evalRPN(vector
     
      & tokens){    if (!tokens.size())return 0;    auto it = tokens.cbegin();    stack
      
       s;    while (it != tokens.cend()){        if ((it->at(0) == '-' && it->size() > 1) || isdigit(it->at(0))){
   //当前字符是数字            s.push(stringToInteger(*it));        }        else{
   //是运算符            if (s.empty())return -1;            int a = s.top();//第一个元素出栈            s.pop();            if (s.empty())return -1;            int b = s.top();//第二个元素出栈            s.pop();            switch (it->at(0))            {            case '+':                s.push(a + b);                break;            case '-':                s.push(b - a);                break;            case '*':                s.push(a * b);                break;            case '/':                if (!a)return -1;                s.push(b / a);                break;            default:                return -1;                break;            }        }        ++it;    }    if (s.empty())return -1;//没有结果    int ret = s.top();    s.pop();    if (s.empty())return ret;    return -1;//栈内元素不止一个}