LeetCode-逆波兰表达式

Evaluate the value of an arithmetic expression inReverse 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

上代码

class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        
        if(tokens.size()==0){
            return 0;
        }
        
        stack<int> rpnST;
        
        for(int i=0;i<tokens.size();i++){
            
            string s = tokens[i];
            
            if(s=="+"||s=="-"||s=="*"||s=="/"){
                
                if(rpnST.size()<2){
                  return 0;
                }
                
                int secondNum = rpnST.top();
                rpnST.pop();
                int firstNum = rpnST.top();
                rpnST.pop();
                int result = getResult(firstNum,secondNum,s);
                rpnST.push(result);     
            }else{
                
                rpnST.push(atoi(s.c_str()));
            }
        }
        
        return rpnST.top();
    }
    
    int getResult(int a,int b,string keyWord){
        
        if(keyWord=="+"){
            return a+b;
        }else if(keyWord=="-"){
            return a-b;
        }else if(keyWord=="*"){
            return a*b;
        }else if(keyWord=="/"){             
            return a/b;
        }else{
            return 0;
        }
    }
};

本题需要先了解一下逆波兰表达式是怎么工作的（编译原理中有讲过，可惜都还给了大学老师）

逆波兰表达式的解释器一般是基于堆栈的。解释过程一般是：操作数入栈；遇到操作符时，操作数出栈，求值，将结果入栈；当一遍后，栈顶就是表达式的值。因此逆波兰表达式的求值使用堆栈结构很容易实现，并且能很快求值。

如 3 + 4
计作 3 4 +
3 入栈
4 入栈
现在的栈内是
  [  4，
     3  ]
现在遇到了运算符 +
那么去栈中取出入栈的两个运算数
4 先出栈，计作secondNum
3 再出栈，计作firstNum
result = firstNum + secondNum
result入栈
现在栈内为
 [
  result
 ]
后面的操作重复这个步骤
最后的结果就是栈顶的数

本题有几个注意点
1、极限的情况（😂永远都别忘了，某个数组长度为0，长度小于三就够不成逆波兰表达式了）
2、栈的特性：先入后出（还有一个特性：除头尾节点之外，每个元素有一个前驱，一个后继。）

现在再回头看代码（简单多了吧）。