（1）计算器题目

在这两次的leetcode刷题中，遇到了几道制作计算器的题目：
stoi 将字符串变为十进制数的函数。
isdigit 判断字符是否为数字的函数。
**num=10*num+int(t-‘0’)**用来表示输入的多位数。

下面贴一段转化为逆波特兰的万能解法

class Solution {
private:
    vector<string> convert(string& s){//这是一个将普通式子转换为逆波特兰的函数！！
        vector<string> tokens;
        tokens.push_back("0"); //处理 -2+1 这种情况
        stack<char> oper;
        int i=0, n=s.length();
        while(i<n){
            if(s[i]==' ') ++i;
            else if(isdigit(s[i])){
                string str = "";
                while(i<n && isdigit(s[i])){
                    str += s[i];
                    ++i;
                }
                tokens.push_back(str);
            }
            else if(s[i]=='('){
                oper.push(s[i]);
                ++i;
            } 
            else if(s[i]==')'){
                while(!oper.empty() && oper.top()!='('){
                    tokens.push_back(string(1, oper.top()));
                    oper.pop();        
                }
                oper.pop();
                ++i;
            }
            else{
                while(!oper.empty() && oper.top()!='('){
                    tokens.push_back(string(1, oper.top()));
                    oper.pop();
                }
                oper.push(s[i]);
                ++i;
            } 
        }
        while(!oper.empty()){
            tokens.push_back(string(1, oper.top()));
            oper.pop();
        }

        return tokens;
    }


    int evalRPN(vector<string>& tokens){//这是在输入为逆波特兰的情况下，使用栈进行计算
        stack<int> stk;
        for(string& str : tokens){
            if(str=="+" || str=="-" || str=="*" || str=="/"){
                int rhs = stk.top();
                stk.pop();
                int lhs = stk.top();
                stk.pop();
                if(str=="+") stk.push(lhs+rhs);
                if(str=="-") stk.push(lhs-rhs);
                if(str=="*") stk.push(lhs*rhs);
                if(str=="/") stk.push(lhs/rhs);
            }
            else{
                stk.push(stoi(str));
            }
        }
        return stk.top();
    }
public:
    int calculate(string s) {
        vector<string> tokens;
        tokens = convert(s);
        return evalRPN(tokens);
    }
};

下面是一段用普通栈直接计算加减法的代码（计算乘除法则更为复杂）

class Solution {
public:
    int calculate(string s) {
        stack<int> ops;
        ops.push(1);
        int sign = 1;

        int ret = 0;
        int n = s.length();
        int i = 0;
        while (i < n) {
            if (s[i] == ' ') {
                i++;
            } else if (s[i] == '+') {
                sign = ops.top();
                i++;
            } else if (s[i] == '-') {
                sign = -ops.top();
                i++;
            } else if (s[i] == '(') {
                ops.push(sign);//将括号前的符号推入栈中
                i++;
            } else if (s[i] == ')') {
                ops.pop();//将之前推入栈中的符号在弹出来
                i++;
            } else {
                long num = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9') {
                    num = num * 10 + s[i] - '0';//输入情况是多位数的时候的经典写法
                    i++;
                }
                ret += sign * num;//将sign作为每个数字的符号！！
            }
        }
        return ret;
    }
};

计算加减乘除但是没有括号的情况，想法是先计算完所有的乘除法，最后在计算法加法！

class Solution {
public:
    int calculate(string s) {
        vector<int> stk;
        char preSign = '+';
        int num = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (isdigit(s[i])) {
                num = num * 10 + int(s[i] - '0');
            }
            if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1) {
                switch (preSign) {
                    case '+':
                        stk.push_back(num);
                        break;
                    case '-':
                        stk.push_back(-num);
                        break;
                    case '*':
                        stk.back() *= num;
                        break;
                    default:
                        stk.back() /= num;
                }
                preSign = s[i];
                num = 0;
            }
        }
        return accumulate(stk.begin(), stk.end(), 0);
    }
};