Java C++刷题leetcode1106解析布尔表达式

目录

• 题目
• 思路：栈【计算器】
• Java
• C++
• Rust
• 总结

题目

题目要求

思路：栈【计算器】

• 和计算器原理类似，分别用两个栈存操作数和操作符，然后到)就开始运算前面的内容，括号里运算都相同所以还是比较简单的。
• 要注意字母t、f和布尔值true、false的转换。

Java

class Solution {
    public boolean parseBoolExpr(String expression) {
        Deque<Character> tfs = new ArrayDeque<>(), opts = new ArrayDeque<>();
        for (char c : expression.toCharArray()) {
            if (c == ',')
                continue;
            else if (c == 't' || c == 'f' || c == '(')
                tfs.addLast(c);
            else if (c == '|' || c == '&' || c == '!')
                opts.addLast(c);
            else if (c == ')') {
                char op = opts.pollLast(), cur = ' ';
                while (!tfs.isEmpty() && tfs.peekLast() != '(') {
                    char top = tfs.pollLast();
                    cur = cur == ' ' ? top : calBool(top, cur, op);
                }
                if (op == '!')
                    cur = cur == 't' ? 'f' : 't';
                tfs.pollLast();
                tfs.addLast(cur);
            }
        }
        return tfs.peekLast() == 't';
    }
    char calBool(char cx, char cy, char op) {
        boolean bx = cx == 't', by = cy == 't';
        boolean res = op == '|' ? bx | by : bx & by;
        return res ? 't' : 'f';
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(n)

C++

class Solution {
public:
    bool parseBoolExpr(string expression) {
        stack<char> tfs, opts;
        for (auto c : expression) {
            if (c == ',')
                continue;
            else if (c == 't' || c == 'f' || c == '(')
                tfs.push(c);
            else if (c == '|' || c == '&' || c == '!')
                opts.push(c);
            else if (c == ')') {
                char op = opts.top(), cur = ' ';
                opts.pop();
                while (!tfs.empty() && tfs.top() != '(') {
                    char top = tfs.top();
                    tfs.pop();
                    cur = cur == ' ' ? top : calBool(top, cur, op);
                }
                if (op == '!')
                    cur = cur == 't' ? 'f' : 't';
                tfs.pop();
                tfs.push(cur);
            }
        }
        return tfs.top() == 't';
    }
    char calBool(char cx, char cy, char op) {
        bool bx = cx == 't', by = cy == 't';
        bool res = op == '|' ? bx | by : bx & by;
        return res ? 't' : 'f';
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)

Rust

impl Solution {
    pub fn parse_bool_expr(expression: String) -> bool {
        let (mut tfs, mut opts) = (vec![], vec![]);
        for c in expression.chars() {
            if c == 't' || c == 'f' || c == '(' {
                tfs.push(c);
            }
            else if c == '|' || c == '&' || c == '!' {
                opts.push(c);
            }
            else if c == ')' {
                let op = opts.pop().unwrap();
                let mut cur = 'e';
                while !tfs.is_empty() && tfs[tfs.len() - 1] != '(' {
                    let top = tfs.pop().unwrap();
                    if cur == 'e' {
                        cur = top;
                    }
                    else { // fn calBool()
                        let (bx, by, mut tmp) = (top == 't', cur == 't', false);
                        if op == '|' {
                            tmp = bx | by;
                        }
                        else {
                            tmp = bx & by;
                        }
                        if tmp {
                            cur = 't';
                        }
                        else {
                            cur = 'f';
                        }
                    }
                }
                if op == '!' { // 非
                    if cur == 't' {
                        cur = 'f';
                    }
                    else {
                        cur = 't';
                    }
                }
                tfs.pop();
                tfs.push(cur);
            }
        }
        tfs.pop().unwrap() == 't'
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(n)

总结

• 像是数据结构里学栈时举的计算器的例子，就循着这个思路感觉不算困难题。
• 当然也可以递归或者只用一个栈，整体思路其实就是巧妙一点的模拟。

以上就是Java C++刷题leetcode1106解析布尔表达式的详细内容，更多关于Java C++解析布尔表达式的资料请关注我们其它相关文章！