Java?C++刷題leetcode1106解析布爾表達式

更新時間：2023年01月16日 14:17:45 作者：AnjaVon

這篇文章主要為大家介紹了Java?C++刷題leetcode1106解析布爾表達式示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

題目

題目要求

思路：棧【計算器】

和計算器原理類似，分別用兩個棧存操作數(shù)和操作符，然后到)就開始運算前面的內(nèi)容，括號里運算都相同所以還是比較簡單的。
要注意字母t、f和布爾值true、false的轉(zhuǎn)換。

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';
    }
}

時間復(fù)雜度：O(n)
空間復(fù)雜度：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';
    }
};

時間復(fù)雜度：O(n)
空間復(fù)雜度：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'
    }
}