在數(shù)據(jù)結(jié)構(gòu)中講到棧的時(shí)候，通常會(huì)講波蘭序和逆波蘭序。但是大學(xué)時(shí)數(shù)據(jù)結(jié)構(gòu)課程真的沒(méi)好好聽(tīng)，基本上都在曠課、玩游戲中度過(guò)，更別提把老師布置的算法題好好做一做研究研究。唉，總要還的。

中綴表達(dá)式（和樹(shù)的中序遍歷）差不多。就是說(shuō)將運(yùn)算符號(hào)看作根的中序表達(dá)。中序表達(dá)式是最符合人類理解的計(jì)算表達(dá)式。但是，對(duì)于計(jì)算機(jī)來(lái)說(shuō)卻不方便，因?yàn)闆](méi)有哪一種簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，可以方便的把表達(dá)式的中間部分抽出來(lái)計(jì)算完再放進(jìn)去繼續(xù)計(jì)算后面的，鏈表也許可以吧，但是代價(jià)應(yīng)該不菲。

波蘭序和逆波蘭序比較適合計(jì)算機(jī)的計(jì)算。

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());
    }
};