Force deduction solution summary 241- design priority for operation expression

Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

Give you a string of numbers and operators  expression , Combine numbers and operators according to different priorities , Calculate and return the results of all possible combinations . You can In any order Return to the answer .

The generated test case meets its corresponding output value in line with 32 Bit integer range , The number of different results does not exceed 104 .

Example 1：

Input ：expression = "2-1-1"
Output ：[0,2]
explain ：
((2-1)-1) = 0 
(2-(1-1)) = 2
Example 2：

Input ：expression = "2*3-4*5"
Output ：[-34,-14,-10,-10,10]
explain ：
(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
 

Tips ：

1 <= expression.length <= 20
expression By numbers and operators '+'、'-' and '*' form .
All integer values in the input expression are in the range [0, 99] 

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/different-ways-to-add-parentheses
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  My thinking efficiency is still relatively low .
*  This problem has nothing to do with symbols , It's the process of pairing each other .
*  So my idea is to split values and symbols first , Divided into two sets , Then start recursive calculation .
*  Each time we traverse the set of values , Then select two adjacent ones for calculation , Then form a new set to enter the next cycle . In this way, each traversal is less than one value , When set length 1 when , Indicates the end of the traversal .

Code ：

public class Solution241 {
    Map<String, Integer> map = new HashMap<>();

    public List<Integer> diffWaysToCompute(String expression) {

        List<String> valueList = new ArrayList<>();
        List<String> symbolList = new ArrayList<>();

        char[] chars = expression.toCharArray();
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i <= chars.length; i++) {
            if (i == chars.length) {
                valueList.add(builder.toString());
                break;
            }
            char aChar = chars[i];
            if (aChar == '+' || aChar == '-' || aChar == '*') {
                valueList.add(builder.toString());
                symbolList.add(String.valueOf(aChar));
                builder.setLength(0);
            } else {
                builder.append(aChar);
            }
        }
        List<Integer> sumList = new ArrayList<>();
        for (String s : valueList) {
            sumList.add(Integer.parseInt(s));
        }
        search(sumList, valueList, symbolList);
        return new ArrayList<>(map.values());
    }

    private void search(List<Integer> sumList, List<String> valueList, List<String> symbolList) {
        if (valueList.size() == 1) {
            String s = valueList.get(0);
            // The result of the calculation is 
            map.put(s, sumList.get(0));
            return;
        }

        for (int i = 0; i < valueList.size() - 1; i++) {
            ArrayList<String> newList = new ArrayList<>(valueList);
            ArrayList<Integer> newNumList = new ArrayList<>(sumList);
            String remove = newList.remove(i);
            Integer leftValue = newNumList.remove(i);

            String s = newList.get(i);
            Integer rightValue = newNumList.get(i);

            String symbol = symbolList.get(i);
            newList.set(i, "(" + remove + symbol + s + ")");
            if (symbol.equals("+")) {
                newNumList.set(i, leftValue + rightValue);
            } else if (symbol.equals("-")) {
                newNumList.set(i, leftValue - rightValue);
            } else {
                newNumList.set(i, leftValue * rightValue);
            }
            symbolList.remove(i);
            search(newNumList, newList, symbolList);
            symbolList.add(i, symbol);
        }
    }
}