241为运算表达式设计优先级

╰+攻爆jí腚メ 2023-02-28 01:30 15阅读 0赞

## 一、前言 ##

分类：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\]这些你需要的都还没算。

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

![20200718233115962.png][]

## 四、编码实现 ##

//==========================================================================
    /*
    * @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;
    }

**执行结果：**

![20200718233232795.png][]

[20200718233115962.png]: /images/20230209/fb7e0d4246f14d2daf416f9e6b98ed47.png
[20200718233232795.png]: /images/20230209/2eb2efdda4414c758c7806e800a7c2a6.png