dfs
暴力搜索所有可能的计算顺序

一个数据栈，一个符号栈，每次数据入栈后，可以选择计算0个~所有个符号，
注意
当数据个数不足两个时，只能计算0个
到末尾时，要把剩下的都计算了，所以如果数据入栈后已经是末尾了就只能选择计算所有个

class Solution {
public:
    vector<int> res;
    vector<int> diffWaysToCompute(string input) {
        stack<int> nums;
        stack<char> op;
        dfs(input, 0, nums, op);
        return res;
    }
    void dfs(string input, int k, stack<int> nums, stack<char> op){
        if(k == input.size()){
            while(op.size()) calc(nums,op);
            res.push_back(nums.top());
            return;
        }
        if(input[k] == '+' || input[k] == '-' || input[k] == '*'){
            op.push(input[k]);
            k++;
        }    
        int x = 0;
        while(k < input.size() && input[k] <= '9' && input[k] >= '0')
            x = x * 10 + (input[k++] - '0');
        nums.push(x);

        dfs(input, k, nums, op);
        //注意k不能到末尾，如果是末尾的话和不计算进行dfs是一样的
        while(nums.size() > 1 && k != input.size()){
            calc(nums, op);
            dfs(input, k, nums, op);
        }
    }
    void calc(stack<int>& nums, stack<char> &op){
        int y = nums.top();
        nums.pop();
        int x = nums. top();
        nums.pop();
        if(op.top() == '+') nums.push(x + y);
        else if(op.top() == '-') nums.push(x - y);
        else nums.push(x * y);
        op.pop();
    }

};