leetcode 241. Different Ways to Add Parentheses | 241. 为运算表达式设计优先级（Java）

本是古典何须时尚 2022-10-10 01:27 114阅读 0赞

## 题目 ##

[https://leetcode.com/problems/different-ways-to-add-parentheses/][https_leetcode.com_problems_different-ways-to-add-parentheses]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

参考：[C++ Solution \[Faster than 100%\] | Explained with diagrams][C_ Solution _Faster than 100_ _ Explained with diagrams]

*  The problem becomes easier when we think about these expressions as expression trees.
 *  We can traverse over the experssion and whenever we encounter an operator, we recursively divide the expression into left and right part and evaluate them seperately until we reach a situation where our expression is purely a number and in this case we can simply return that number.
 *  Since there can be multiple ways to evaluate an expression (depending on which operator you take first) we will get a list of reults from left and the right part.
 *  Now that we have all the possible results from the left and the right part, we can use them to find out all the possible results for the current operator.

import java.util.ArrayList;
    import java.util.List;
    
    class Solution { 
        public boolean isOp(char c) { 
            return c == '+' || c == '-' || c == '*' || c == '/';
        }
    
        public int cal(int a, char op, int b) { 
            return switch (op) { 
                case '+' -> a + b;
                case '-' -> a - b;
                case '*' -> a * b;
                default -> a / b;
            };
        }
    
        public List<Integer> diffWaysToCompute(String expression) { 
            char[] exp = expression.toCharArray();
            List<Integer> list = new ArrayList<>();
            boolean numberOnly = true;
            for (int i = 0; i < exp.length; i++) { 
                List<Integer> left = new ArrayList<>();
                List<Integer> right = new ArrayList<>();
                if (isOp(exp[i])) { 
                    numberOnly = false;
                    left = diffWaysToCompute(expression.substring(0, i));
                    right = diffWaysToCompute(expression.substring(i + 1, exp.length));
                }
                for (int j : left) { 
                    for (int k : right) { 
                        list.add(cal(j, exp[i], k));
                    }
                }
            }
            if (numberOnly) list.add(Integer.valueOf(expression));
            return list;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_different-ways-to-add-parentheses]: https://leetcode.com/problems/different-ways-to-add-parentheses/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/a6f270c416664e959b40a3a4bc1a9bb0.png
[C_ Solution _Faster than 100_ _ Explained with diagrams]: https://leetcode.com/problems/different-ways-to-add-parentheses/discuss/1294189/C++-Solution-Faster-than-100-or-Explained-with-diagrams
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221005/76086c28bc1a4b80abedcb8d07b801da.png