leetcode 282. Expression Add Operators | 282. 给表达式添加运算符（中缀表达式求值）

「爱情、让人受尽委屈。」 2022-08-28 13:41 3阅读 0赞

## 题目 ##

[https://leetcode.com/problems/expression-add-operators/description/][https_leetcode.com_problems_expression-add-operators_description]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

中缀表达式求值问题，参考：[leetcode 227. Basic Calculator II | 227. 基本计算器 II（中缀表达式求值）][leetcode 227. Basic Calculator II _ 227. _ II]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
本题主要是两个回溯，第一个回溯用来切割数字，第二个回溯用来插入运算符。以上两项工作做完后，用经典的中缀表达式求值，计算是否为 target 即可。

class Solution { 
        int N;
        List<String> result;
        HashMap<String, Integer> priorityMap; // 运算符优先级
        String[] ops;
    
        public void initPriorityMap() { 
            priorityMap = new HashMap<>();
            priorityMap.put("+", 0);
            priorityMap.put("-", 0);
            priorityMap.put("*", 1);
            // priorityMap.put("/", 1);
        }
    
        public List<String> addOperators(String num, int target) { 
            N = num.length();
            result = new ArrayList<>();
            ops = new String[]{ "+", "-", "*"};
            initPriorityMap();
            splitNums(num, 0, target, new LinkedList<>());
            return result;
        }
    
        public void splitNums(String num, int i, int target, Deque<Integer> queue) {  // 回溯1：尝试所有分割数字方式
            if (i == N) { 
                genExp(queue, target, new LinkedList<>());
            }
            for (int j = i + 1; j <= N; j++) { 
                String sub = num.substring(i, j);
                if (sub.startsWith("0") && sub.length() > 1 || Long.parseLong(sub) > Integer.MAX_VALUE) continue;
                queue.add(Integer.valueOf(sub)); // [...)
                splitNums(num, j, target, queue);
                queue.removeLast();
            }
        }
    
        public void genExp(Deque<Integer> queue, int target, Deque<String> exp) {  // 回溯2：尝试所有运算符，生成中缀表达式
            Deque<Integer> q = new LinkedList<>(queue);
    
            if (q.size() == 1) { 
                exp.add(String.valueOf(q.pollFirst()));
    // System.out.println(exp);
                Integer res = calExpression(exp, target);
                if (res == target) { 
                    StringBuilder sb = new StringBuilder();
                    for (String s : exp) { 
                        sb.append(s);
                    }
                    result.add(sb.toString());
                }
                exp.pollLast();
                return;
            }
    
            exp.add(String.valueOf(q.pollFirst()));
            for (String op : ops) { 
                exp.add(op);
                genExp(q, target, exp);
                exp.pollLast();
            }
            exp.pollLast();
        }
    
        public Integer calExpression(Deque<String> exp, int target) {  // 中缀表达式求值
            Stack<Integer> s1 = new Stack<>(); // 操作数栈
            Stack<String> s2 = new Stack<>(); // 运算符栈
            boolean isNum = false;
            Deque<String> q = new LinkedList<>(exp);
            while (!q.isEmpty()) { 
                isNum = !isNum;
                String val = q.pollFirst();
                if (isNum) {  // 是数字
                    s1.push(Integer.valueOf(val));
                } else {  // 是运算符
                    if (s2.isEmpty() || isPrior(val, s2.peek())) {  // 若当前运算符大于栈顶运算符优先级 则入栈
                        s2.push(val);
                    } else {  // 否则 在当前运算符小于等于栈顶运算符情况下 不断出栈并运算 将运算结果入操作数栈
                        while (s2.size() > 0 && !isPrior(val, s2.peek())) { 
                            String op = s2.pop();
                            Integer n1 = s1.pop();
                            Integer n2 = s1.pop();
                            int res = cal(n1, n2, op);
                            s1.push(res);
                        }
                        s2.push(val);
                    }
                }
            }
            while (!s2.isEmpty()) {  // 运算符栈中还有剩余 则一直出栈并运算
                String op = s2.pop();
                Integer n1 = s1.pop();
                Integer n2 = s1.pop();
                int res = cal(n1, n2, op);
                s1.push(res);
            }
            return s1.pop();
        }
    
        public int cal(int n1, int n2, String op) { 
            switch (op) { 
                case "+":
                    return n2 + n1;
                case "-":
                    return n2 - n1;
                case "*":
                    return n2 * n1;
                default:
                    System.out.println("op err");
                    return -1;
            }
        }
    
        public boolean isPrior(String op1, String op2) { 
            return priorityMap.get(op1) > priorityMap.get(op2);
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]

[https_leetcode.com_problems_expression-add-operators_description]: https://leetcode.com/problems/expression-add-operators/description/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d5a01ee97b854a65a9c7a2ed205b985e.png
[leetcode 227. Basic Calculator II _ 227. _ II]: https://blog.csdn.net/sinat_42483341/article/details/118083945
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/24061678222846c780bc86d842d67d78.jpg?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5a-S5rOJSHE=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/d28001adaa1649a280e87f37fed7b96c.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5a-S5rOJSHE=,size_20,color_FFFFFF,t_70,g_se,x_16