1106. 解析布尔表达式

Posted on In , Views: Disqus: Reading time ≈ 1 mins.

给你一个以字符串形式表述的 布尔表达式（boolean） expression，返回该式的运算结果。
有效的表达式需遵循以下约定：

  • “t”，运算结果为 True
  • “f”，运算结果为 False
  • “!(expr)”，运算过程为对内部表达式 expr 进行逻辑 非的运算（NOT）
  • “&(expr1,expr2,…)”，运算过程为对 2 个或以上内部表达式 expr1, expr2, … 进行逻辑 与的运算（AND）
  • “|(expr1,expr2,…)”，运算过程为对 2 个或以上内部表达式 expr1, expr2, … 进行逻辑 或的运算（OR）

递归

截取子表达式字符串，每个字符串递归，效率较低

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
class Solution {
    public boolean parseBoolExpr(String expression) {
        if ("t".equals(expression)) return true;
        if ("f".equals(expression)) return false;

        // 获取标志位
        char sign = expression.charAt(0);
        // 分解内部表达式 
        // e.g.|(&(t,f,t),!(t)) => [&(t,f,t), !(t)]
        List<String> innerExps = getInnerExpression(expression);

        // !
        if (sign == '!') return !parseBoolExpr(innerExps.get(0));

        // &
        if (sign == '&') {
            for (String innerExp : innerExps) {
                if (!parseBoolExpr(innerExp)) return false;
            }
            return true;
        }

        // |
        if (sign == '|') {
            for (String innerExp : innerExps) {
                if (parseBoolExpr(innerExp)) return true;
            }
            return false;
        }

        return false;
    }

    private List<String> getInnerExpression(String exp) {
        // exp <=> !(innerExpStr)
        String innerExpStr = exp.substring(2, exp.length() - 1);
        char[] innerExpCharArray = innerExpStr.toCharArray();

        List<String> result = new ArrayList();
        int bracketsNumDiff = 0;
        int preIndex = 0;
        for (int i = 0; i < innerExpCharArray.length; i++) {
            if (innerExpCharArray[i] == '(') {
                bracketsNumDiff++;
                continue;
            }
            if (innerExpCharArray[i] == ')') {
                bracketsNumDiff--;
                continue;
            }

            // 逗号时判断
            if (bracketsNumDiff == 0 && innerExpCharArray[i] == ',') {
                result.add(innerExpStr.substring(preIndex, i));
                // preIndex 设为逗号后的点，i 跳过 preIndex
                preIndex = i++ + 1;
            }
        }
        result.add(innerExpStr.substring(preIndex));
        return result;
    }
}

优化后的递归，使用全局索引

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
class Solution {
    int index = 0;
    public boolean parseBoolExpr(String expression) {
            if (expression.charAt(index) == 't') {
                index++;
                return true;
            }
            if (expression.charAt(index) == 'f') {
                index++;
                return false;
            }
            if (expression.charAt(index) == '!') {
                index += 2;
                boolean t = parseBoolExpr(expression);
                index++;
                return !t;
            }
            if (expression.charAt(index) == '&') {
                boolean t = true;
                index++;
                do {
                    index++;
                    t &= parseBoolExpr(expression);
                } while (expression.charAt(index) == ',');
                index++;
                return t;
            }
            if (expression.charAt(index) == '|') {
                boolean t = false;
                index++;
                do {
                    index++;
                    t |= parseBoolExpr(expression);
                }
                while (expression.charAt(index) == ',');
                index++;
                return t;
            }
            return false;
        }
}

栈