241为运算表达式设计优先级-蒲公英云

一、前言

分类：Divide and Conquer。

问题来源LeetCode 241 难度：中等。

问题链接：https://leetcode-cn.com/problems/different-ways-to-add-parentheses

二、题目

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例1：

输入: "2-1-1"
输出: [0, 2]
解释: 
((2-1)-1) = 0 
(2-(1-1)) = 2

示例 2:

输入: "2*3-4*5"
输出: [-34, -14, -10, -10, 10]
解释: 
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

三、思路

这里提供两种解决方法。

方法一：分治法。以操作符为界限，将运算表达式分割为两个不同的部分，在递归计算（在这个运算符处分割，其实也是代表将这个运算符最后一个算）递归终止条件：字符串中就一个数字在递归的过程中，会有一部分字符串会重复多次计算，所以在前面的基础上加入哈希表，同空间换时间，执行速度会快些。

方法二：动态规划。首先将字符串中的数字和操作符分别存储下来第i个操作符对应的数字是i和i+1，同理第i个数的前面的操作符是i-1，后面的一个是i（i表示在数组中的序号）dp[i][j]表示从第i个数字到第j个数字的所有情况

（1）i==j 等于数字本身的值

（2）i != j(j肯定是大于i的)

将i-j分成两个式子来看，[i,i]op[i+1,j],[i,i+1]op[i+2,j]…[[i,j-1]]op[j,j]

将上面的所有情况全部组合起来。[i,i+k]op[i+k+1,j]，op是ops数组里面的ops[i+k]。

有了以上，我们就可以写出动态规划了，还有一个需要注意的地方是，（2）情况也就是一个遍历，但是遍历的顺序需要注意，不应该是[0,j]->[j-1,j]而应该是[j-1,j]->[0->j]。如果是从[0,j]开始，你会发现[1,j]..[j-1,j]这些你需要的都还没算。

下面是另外一种理解说明，思路和上面一样。

四、编码实现

//==========================================================================
/*
* @file    : 241_DiffWaysToCompute.h
* @label   : Divide and Conquer
* @blogs   : https://blog.csdn.net/nie2314550441/article/details/107437244
* @author  : niebingyu
* @date    : 2020/07/18
* @title   : 241.为运算表达式设计优先级
* @purpose : 给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。
* 你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
*
* 示例1：
* 输入: "2-1-1"
* 输出: [0, 2]
* 解释:
* ((2-1)-1) = 0
* (2-(1-1)) = 2
* 
* 示例2：
* 输入: "2*3-4*5"
* 输出: [-34, -14, -10, -10, 10]
* 解释:
* (2*(3-(4*5))) = -34
* ((2*3)-(4*5)) = -14
* ((2*(3-4))*5) = -10
* (2*((3-4)*5)) = -10
* (((2*3)-4)*5) = 10
*
* 来源：力扣（LeetCode）
* 难度：中等
* 链接：https://leetcode-cn.com/problems/different-ways-to-add-parentheses
*/
//==========================================================================
#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
#define NAMESPACE_DIFFWAYSTOCOMPUTE namespace NAME_DIFFWAYSTOCOMPUTE {
#define NAMESPACE_DIFFWAYSTOCOMPUTEEND }
NAMESPACE_DIFFWAYSTOCOMPUTE
/*
分治归并
    以操作符为界限，将运算表达式分割为两个不同的部分，在递归计算（在这个运算符处分割，其实也是代表将这个运算符最后一个算）
    递归终止条件：字符串中就一个数字
    在递归的过程中，会有一部分字符串会重复多次计算，所以在前面的基础上加入哈希表，同空间换时间，时间确实快了，从12ms->4ms
*/
// 方法一，分治法
class Solution_1 
{
public:
    vector<int> diffWaysToCompute(string input) 
    {
        int index = 0;
        int num = 0;
        while(index < input.size() && isdigit(input[index]))
            num = num * 10 + input[index++] - '0';
        if(index == input.size())
        {
            hash[input] = { num };
            return { num };
        }
        vector<int> ans;
        for(int i = 0; i < input.size(); i++)
        {
            if(isOp(input[i]))
            {
                string s1 = input.substr(0, i);
                string s2 = input.substr(i);
                vector<int> result1, result2;
                if(!hash.count(s1))
                    result1 = diffWaysToCompute(input.substr(0, i));
                else
                    result1 = hash[s1];
                if(!hash.count(s2))
                    result2 = diffWaysToCompute(input.substr(i+1));
                else
                    result2 = hash[s2];
                for(int r1 : result1)
                {
                    for(int r2 : result2)
                    {
                        ans.push_back(calculate(r1, input[i] ,r2));
                    }
                }
            }
        }
        hash[input] = ans;
        return ans;
    }
    bool isOp(const char& c)
    {
        return c == '+' || c == '-' || c == '*';
    }
    int calculate(const int& num1, const char& op, const int& num2){
        if(op == '+')
            return num1 + num2;
        else if(op == '-')
            return num1 - num2;
        else
            return num1 * num2;
    }
private:
    unordered_map<string,vector<int>> hash;
};
// 方法二，动态规划
class Solution_2
{
public:
    vector<int> diffWaysToCompute(string input) 
    {
        vector<int> nums;
        vector<char> ops;
        int num = 0;
        for(int i = 0; i < input.size(); i++)
        {
            if(isOp(input[i]))
            {
                nums.push_back(num);
                ops.push_back(input[i]);
                num = 0;
            }
            else
                num = num * 10 + input[i] - '0';
        }
        nums.push_back(num);
        int n = nums.size();
        vector<vector<vector<int>>> dp(n,vector<vector<int>>(n));
        for(int i = 0; i < n; i++)
            dp[i][i].push_back(nums[i]);
        for(int j = 1; j < n; j++)
        {
            for(int i = j-1; i >= 0; i--)
            {
                for(int k = i; k < j; k++)
                {
                    for(int r1 : dp[i][k])
                    {
                        for(int r2 : dp[k+1][j])
                        {
                            dp[i][j].push_back(calculate(r1,ops[k],r2));
                        }
                    }
                }
            }
        }
        return dp[0][n-1];
    }
    bool isOp(const char& c)
    {
        return c == '+' || c == '-' || c == '*';
    }
    int calculate(const int& num1, const char& op, const int& num2){
        if(op == '+')
            return num1 + num2;
        else if(op == '-')
            return num1 - num2;
        else
            return num1 * num2;
    }
};
以下为测试代码//
// 测试 用例 START
void test(const char* testName, string input, vector<int> expect)
{
    Solution_1 s1;
    vector<int> result1 = s1.diffWaysToCompute(input);
    sort(result1.begin(), result1.end());
    Solution_2 s2;
    vector<int> result2 = s2.diffWaysToCompute(input);
    sort(result2.begin(), result2.end());
    if (result1 == expect && result2 == expect)
        cout << testName << ", solution passed." << endl;
    else
        cout << testName << ", solution failed. " << endl;
}
// 测试用例
void Test1()
{
    string input = "2*3-4*5";
    vector<int> expect = { -34, -14, -10, -10, 10 };
    test("Test1()", input, expect);
}
NAMESPACE_DIFFWAYSTOCOMPUTEEND
// 测试 用例 END
//
void DiffWaysToCompute_Test()
{
    cout << "------ start 241.为运算表达式设计优先级 ------" << endl;
    NAME_DIFFWAYSTOCOMPUTE::Test1();
    cout << "------ end 241.为运算表达式设计优先级 --------" << endl;
}