lintcode 367 · 表达树构造 【hard 栈，树】

题目

https://www.lintcode.com/problem/367

表达树是一个二叉树的结构，用于衡量特定的表达。所有表达树的叶子都有一个数字字符串值。而所有表达树的非叶子都有一个操作字符串值。

给定一个表达数组，请构造该表达的表达树，并返回该表达树的根。

什么是表达树？详见wiki百科：
表达树

样例
样例 1:

输入: ["2","*","6","-","(","23","+","7",")","/","(","1","+","2",")"]
输出: {[-],[*],[/],[2],[6],[+],[+],#,#,#,#,[23],[7],[1],[2]} 
解释:
其表达树如下：

	                 [ - ]
	             /          \
	        [ * ]              [ / ]
	      /     \           /         \
	    [ 2 ]  [ 6 ]      [ + ]        [ + ]
	                     /    \       /      \
	                   [ 23 ][ 7 ] [ 1 ]   [ 2 ] .

在构造该表达树后，你只需返回根节点`[-]`。
样例 2:

输入: ["10","+","(","3","-","5",")","+","7","*","7","-","2"]
输出: {[-],[+],[2],[+],[*],#,#,[10],[-],[7],[7],#,#,[3],[5]}
解释:
其表达树如下：
 	                       [ - ]
	                   /          \
	               [ + ]          [ 2 ]
	           /          \      
	       [ + ]          [ * ]
              /     \         /     \
	  [ 10 ]  [ - ]    [ 7 ]   [ 7 ]
	          /    \ 
                [3]    [5]
在构造该表达树后，你只需返回根节点`[-]`。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

思路

这种题目要多练习

   解题思路
    跟370题转换成逆波兰表达式几乎一样，也是维护单调栈，不断弹出优先级更高的操作符
    和另一个栈的树节点组成新子树再加入回栈。
    最后就会计算成一个根节点加回栈里，这个时候栈顶元素也是唯一元素就是根节点
    例如：2 * 6 - (23 + 7)
    遇到2和6，建立树节点加入树节点Stack
    遇到*，加入操作符Stack
    遇到-，优先级低于*，弹出和树节点Stack里2个元素，组成新节点（左子树是2，
    右子树是6），放回树节点Stack
    后面规则一样
1
2
3
4
5
6
7
8
9
10

答案

/**
 * Definition of ExpressionTreeNode:
 * public class ExpressionTreeNode {
 *     public String symbol;
 *     public ExpressionTreeNode left, right;
 *     public ExpressionTreeNode(String symbol) {
 *         this.symbol = symbol;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param expression: A string array
     * @return: The root of expression tree
     */
    public ExpressionTreeNode build(String[] expression) {
         /*
    解题思路
    跟370题转换成逆波兰表达式几乎一样，也是维护单调栈，不断弹出优先级更高的操作符和另一个栈的树节点组成新子树再加入回栈。
    最后就会计算成一个根节点加回栈里，这个时候栈顶元素也是唯一元素就是根节点
    例如：2 * 6 - (23 + 7)
    遇到2和6，建立树节点加入树节点Stack
    遇到*，加入操作符Stack
    遇到-，优先级低于*，弹出和树节点Stack里2个元素，组成新节点（左子树是2，右子树是6），放回树节点Stack
    后面规则一样
     */
        if (expression == null || expression.length == 0)
            return null;
        Map<String, Integer> prio = new HashMap<>();
        getPrio(prio); //优先级

        int n = expression.length;
        Stack<String> sign = new Stack<>();
        Stack<ExpressionTreeNode> nums = new Stack<>();
        for (int i = 0; i <= n; i++) {
            String ele = "#";  //数组最后一个位置的后面#
            if (i < n)
                ele = expression[i];

            if (ele.equals("(")) {
                sign.push(ele);
            }
            // 遇到右括号时候弹出操作符直到遇到左括号，每一个操作符弹出两个操作数，
            // 也可能是别的操作符节点建立树结构
            else if (ele.equals(")")) {
                while (!sign.isEmpty() && !sign.peek().equals("(")) {
                    String op = sign.pop();
                    ExpressionTreeNode R = nums.pop();
                    ExpressionTreeNode L = nums.pop();
                    ExpressionTreeNode node = new ExpressionTreeNode(op);
                    node.left = L;
                    node.right = R;
                    nums.add(node);
                }
                sign.pop(); //去掉左括号
            } else if (prio.containsKey(ele)) { //是否在优先级列表中，已经去掉了左括号的
                //弹出优先级高的操作符建立树结构
                while (!sign.isEmpty() && prio.get(sign.peek()) >= prio.get(ele)) {
                    ExpressionTreeNode node = new ExpressionTreeNode(sign.pop());
                    ExpressionTreeNode R = nums.pop();
                    ExpressionTreeNode L = nums.pop();
                    node.left = L;
                    node.right = R;
                    nums.add(node);
                }

                sign.add(ele);
            } else {
                nums.add(new ExpressionTreeNode(ele)); //数字
            }
        }

        if (nums.isEmpty()) return null;
        return nums.peek();
    }
     public static void getPrio(Map<String, Integer> prio) {
        prio.put("#", 0);
        prio.put("(", 1);
        prio.put("+", 2);
        prio.put("-", 2);
        prio.put("*", 3);
        prio.put("/", 3);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86