题解 | #给表达式添加运算符#

介于数据规模较小，暴力dfs求解即可。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @param target int整型 
     * @return string字符串vector
     */
    vector<string> ans;
    map<char,int> opt = {{'+',1},{'-',1},{'*',2}};
    void dfs(string num,int target,int start,string temp){
        if(start == num.size()){
            stack<int> num_stack;
            stack<char> opt_stack;
            int i = 0;
            while(!(num_stack.size() == 1 && i == temp.size())){
                if(temp[i] <= '9' && temp[i] >= '0'){
                    num_stack.push(temp[i] - '0');
                    ++i;
                }
                else{
                    if(opt_stack.empty()){
                        opt_stack.push(temp[i]);
                        ++i;
                    }
                    else{
                        if((opt_stack.size() == 1 && i == temp.size() )|| opt[opt_stack.top()] >= opt[temp[i]]){
                            int b = num_stack.top();
                            num_stack.pop();
                            int a = num_stack.top();
                            num_stack.pop();
                            if(opt_stack.top() == '+')
                                num_stack.push(a + b);
                            else if(opt_stack.top() == '-')
                                num_stack.push(a - b); 
                            else
                                num_stack.push(a * b);
                            opt_stack.pop();
                        }
                        else{
                            opt_stack.push(temp[i]);
                            ++i;
                        }
                    }
                }
            }
            if(num_stack.top() == target)
                ans.push_back(temp);
            return;
        }
        dfs(num,target,start + 1,temp + '+' + num[start]);
        dfs(num,target,start + 1,temp + '-' + num[start]);
        dfs(num,target,start + 1,temp + '*' + num[start]);
    }
    vector<string> addOpt(string num, int target) {
        // write code here
        string temp(1,num[0]);
        dfs(num,target,1,temp);
        return ans;
    }
};