LeetCode 1106. 解析布尔表达式

Categories:

题目描述
思路分析
1. 解法一：栈解析（推荐）
相似题目

题目描述

✅ 1106. 解析布尔表达式

思路分析

解法一：栈解析（推荐）

核心思路：

使用栈逐字符解析，遇到 ) 时弹出直到 (。

根据操作符 !、&、| 计算子表达式结果。

将结果再压栈，继续解析。

复杂度分析：

时间复杂度：O(n)，其中 n 表示表达式长度。

空间复杂度：O(n)，用于栈。

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public boolean parseBoolExpr(String expression) {
        Deque<Character> stack = new ArrayDeque<>();

        for (char c : expression.toCharArray()) {
            if (c == ',') {
                continue;
            }
            if (c != ')') {
                stack.push(c);
                continue;
            }

            int trueCount = 0;
            int falseCount = 0;
            while (stack.peek() != '(') {
                char val = stack.pop();
                if (val == 't') {
                    trueCount++;
                } else if (val == 'f') {
                    falseCount++;
                }
            }
            stack.pop();

            char op = stack.pop();
            char res;
            if (op == '!') {
                res = (falseCount == 1) ? 't' : 'f';
            } else if (op == '&') {
                res = (falseCount == 0) ? 't' : 'f';
            } else {
                res = (trueCount > 0) ? 't' : 'f';
            }

            stack.push(res);
        }

        return stack.peek() == 't';
    }
}

func parseBoolExpr(expression string) bool {
	stack := make([]byte, 0)

	for i := 0; i < len(expression); i++ {
		c := expression[i]
		if c == ',' {
			continue
		}
		if c != ')' {
			stack = append(stack, c)
			continue
		}

		trueCount, falseCount := 0, 0
		for len(stack) > 0 && stack[len(stack)-1] != '(' {
			val := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			if val == 't' {
				trueCount++
			} else if val == 'f' {
				falseCount++
			}
		}
		stack = stack[:len(stack)-1]

		op := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		var res byte
		if op == '!' {
			if falseCount == 1 {
				res = 't'
			} else {
				res = 'f'
			}
		} else if op == '&' {
			if falseCount == 0 {
				res = 't'
			} else {
				res = 'f'
			}
		} else {
			if trueCount > 0 {
				res = 't'
			} else {
				res = 'f'
			}
		}

		stack = append(stack, res)
	}

	return stack[len(stack)-1] == 't'
}

相似题目

题目	难度	考察点
150. 逆波兰表达式求值	中等	栈
224. 基本计算器	困难	栈
227. 基本计算器 II	中等	栈
772. 基本计算器 III	困难	栈
394. 字符串解码	中等	栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/87972596