在数据结构中讲到栈的时候，通常会讲波兰序和逆波兰序。但是大学时数据结构课程真的没好好听，基本上都在旷课、玩游戏中度过，更别提把老师布置的算法题好好做一做研究研究。唉，总要还的。

中缀表达式（和树的中序遍历）差不多。就是说将运算符号看作根的中序表达。中序表达式是最符合人类理解的计算表达式。但是，对于计算机来说却不方便，因为没有哪一种简单的数据结构，可以方便的把表达式的中间部分抽出来计算完再放进去继续计算后面的，链表也许可以吧，但是代价应该不菲。

波兰序和逆波兰序比较适合计算机的计算。

class Solution {
    bool isNotation(string input) {
    int size = input.size();
    if (size == 1) {
        if (input[0]=='+'||input[0]=='-'||input[0]=='*'||input[0]=='/') {
            return true;
        } else {
            return false;
        }
    }
    return false;
}
int convertInt(string input){
int ret=0;
    if(input[0]=='-'){
        for(int i=1;i<input.size();i++){
            ret+=(input[input.size()-i]-'0')*pow(10,(i-1));
        }
        return 0-ret;
    }else{
        for(int i=0;i<input.size();i++){
            ret+=(input[input.size()-1-i]-'0')*pow(10,(i));
        }
        return ret;
    }
}
public:
    int evalRPN(vector<string>& tokens) {
    int i=0;
    int size=tokens.size();
    stack<string> temp;
    while(i<size){
        if(!isNotation(tokens[i])){
            temp.push(tokens[i]);
        }else{
            string second=temp.top();
            temp.pop();
            string first=temp.top();
            temp.pop();
            int hh;
            if(tokens[i]=="+"){
                hh=convertInt(first)+convertInt(second);
            }
            else if(tokens[i]=="-"){
                hh=convertInt(first)-convertInt(second);
            }
            else if(tokens[i]=="*"){
                hh=convertInt(first)*convertInt(second);
            }
            else if(tokens[i]=="/"){
                hh=convertInt(first)/convertInt(second);
            }
            temp.push(to_string(hh));
        }
        i++;
    }
    return stoi(temp.top());
    }
};