Daily LeetCode – day0099 1106. Parsing A Boolean Expression

import java.util.Stack;

// 1106. Parsing A Boolean Expression
class Solution {
    public boolean parseBoolExpr(String expression) {
        Stack<Character> stack = new Stack<>();
        char[] charArray = expression.toCharArray();
        for (char c : charArray) {
            if (c == 't' || c == 'f' || c == '!' || c == '&' || c == '|') {
                stack.push(c);
            } else if (c == ')') {
                boolean hasTrue = false;
                boolean hasFalse = false;
                while (stack.peek() == 't' || stack.peek() == 'f') {
                    if (stack.pop() == 't') {
                        hasTrue = true;
                    } else {
                        hasFalse = true;
                    }
                }
                char operator = stack.pop();
                char preIn;
                if (operator == '!') {
                    preIn = hasTrue ? 'f' : 't';
                } else if (operator == '&') {
                    preIn = hasFalse ? 'f' : 't';
                } else {
                    preIn = hasTrue ? 't' : 'f';
                }
                stack.push(preIn);
            }
        }
        return stack.peek() == 't';
    }
}
学习笔记:
这是一道困难题,用到的是栈。
根据不同的字符来进行处理,先在纸上推演几遍,然后写成代码就可以一气呵成。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注