2023-07-19：布尔表达式 是计算结果不是 true 就是 false 的表达式
有效的表达式需遵循以下约定：
't'，运算结果为 true
'f'，运算结果为 false
'!(subExpr)'，运算过程为对内部表达式 subExpr 进行 逻辑非（NOT）运算
'&(subExpr1, subExpr2, ..., subExprn)'
运算过程为对 2 个或以上内部表达式
subExpr1, subExpr2, ..., subExprn 进行 逻辑与（AND）运算
'|(subExpr1, subExpr2, ..., subExprn)'
运算过程为对 2 个或以上内部表达式
subExpr1, subExpr2, ..., subExprn 进行 逻辑或（OR）运算
给你一个以字符串形式表述的 布尔表达式 expression，返回该式的运算结果。
题目测试用例所给出的表达式均为有效的布尔表达式，遵循上述约定。
输入：expression = "&(|(f))"。
输出：false。
答案 2023-07-19：
大体过程如下：
1.主函数main中定义了一个布尔表达式expression为"&(|(f))"，该表达式需要计算结果。
2.调用parseBoolExpr函数，并将布尔表达式作为参数传递给它。
3.parseBoolExpr函数中定义了一个内部递归函数f，接收两个参数：表达式字符串exp和当前字符索引index。
4.函数f中首先获取当前索引处的字符judge，判断其类型。
5.如果judge为't'，返回结果为 true，索引保持不变。
6.如果judge为'f'，返回结果为 false，索引保持不变。
7.如果judge为其他字符，进行进一步判断。
8.如果judge为'!'，则递归调用f函数，并将索引加 1 作为参数，获取递归调用的结果next，对该结果执行逻辑非运算，返回结果为!next.ans，索引更新为next.end + 1。
9.如果judge为'&'或'|'，则设置布尔变量ans为相应的值（true 或 false），并在循环中处理多个子表达式。
10.在循环中，当当前字符不是')'时，执行以下操作：
- 如果当前字符是','，则将索引加1，跳过逗号字符。
- 否则，递归调用`f`函数，并将当前索引作为参数获取递归结果`next`。
- 根据父表达式的运算符进行相应的逻辑运算，更新布尔变量`ans`的值。
- 更新索引为`next.end + 1`。
复制代码
11.循环结束后，返回结果为Info{ans, index}，其中ans为布尔表达式的计算结果，index为当前索引。
12.返回到parseBoolExpr函数，获取f函数的结果Info，返回Info.ans作为布尔表达式的最终计算结果。
13.输出最终结果。根据给定的表达式"&(|(f))"，计算结果为 false，打印结果 false。
时间复杂度：假设表达式字符串的长度为 n，递归过程涉及到遍历字符串中的每个字符，因此时间复杂度为 O(n)。
空间复杂度：递归调用过程中会使用额外的栈空间来保存递归的状态，最坏情况下递归的深度可以达到 n，因此空间复杂度为 O(n)。
go 完整代码如下：
package main
import ( "fmt")
type Info struct { ans bool end int}
func parseBoolExpr(expression string) bool { return f([]rune(expression), 0).ans}
func f(exp []rune, index int) Info { judge := exp[index] if judge == 'f' { return Info{false, index} } else if judge == 't' { return Info{true, index} } else { var ans bool index += 2 if judge == '!' { next := f(exp, index) ans = !next.ans index = next.end + 1 } else { ans = judge == '&' for exp[index] != ')' { if exp[index] == ',' { index++ } else { next := f(exp, index) if judge == '&' { if !next.ans { ans = false } } else { if next.ans { ans = true } } index = next.end + 1 } } } return Info{ans, index} }}
func main() { expression := "&(|(f))" result := parseBoolExpr(expression) fmt.Println(result)}
复制代码
rust 代码如下：
fn main() { let expression = "&(|(f))"; let result = parse_bool_expr(expression.to_string()); println!("{}", result);}
fn parse_bool_expr(expression: String) -> bool { let exp: Vec<char> = expression.chars().collect(); let info = f(&exp, 0); info.ans}
struct Info { ans: bool, end: usize,}
fn f(exp: &[char], index: usize) -> Info { let judge = exp[index]; if judge == 'f' { return Info { ans: false, end: index, }; } else if judge == 't' { return Info { ans: true, end: index, }; } else { let mut ans: bool; let mut index = index + 2; if judge == '!' { let next = f(exp, index); ans = !next.ans; index = next.end + 1; } else { ans = judge == '&'; while exp[index] != ')' { if exp[index] == ',' { index += 1; } else { let next = f(exp, index); if judge == '&' { if !next.ans { ans = false; } } else { if next.ans { ans = true; } } index = next.end + 1; } } } Info { ans, end: index } }}
复制代码
c++完整代码如下：
#include <iostream>#include <string>
using namespace std;
struct Info { bool ans; // 结束下标！ int end;
Info(bool a, int e) { ans = a; end = e; }};
Info f(const string& exp, int index) { char judge = exp[index]; if (judge == 'f') { return Info(false, index); } else if (judge == 't') { return Info(true, index); } else { // ! // & // | // 再说！
bool ans;
// ! ( ? // i i+1 i+2 // & ( ? // i i+1 i+2 // | ( ? // i i+1 i+2 index += 2; if (judge == '!') { // ! ( ?...... ) // i i+1 i+2 Info next = f(exp, index); ans = !next.ans; index = next.end + 1; } else { // & // i // judge == '&' 或者 judge == '|' ans = judge == '&'; while (exp[index] != ')') { if (exp[index] == ',') { index++; } else { Info next = f(exp, index); if (judge == '&') { if (!next.ans) { ans = false; } } else { if (next.ans) { ans = true; } } index = next.end + 1; } } } return Info(ans, index); }}
bool parseBoolExpr(const string& expression) { return f(expression, 0).ans;}
int main() { string expression = "&(|(f))"; cout << boolalpha << parseBoolExpr(expression) << endl; return 0;}
复制代码
c 完整代码如下：
#include <stdbool.h>#include<stdio.h>
typedef struct Info { bool ans; int end;} Info;
Info f(char* exp, int index);
bool parseBoolExpr(char* expression) { return f(expression, 0).ans;}
Info f(char* exp, int index) { char judge = exp[index]; Info info;
if (judge == 'f') { info.ans = false; info.end = index; } else if (judge == 't') { info.ans = true; info.end = index; } else { bool ans; index += 2;
if (judge == '!') { Info next = f(exp, index); ans = !next.ans; index = next.end + 1; } else { ans = judge == '&';
while (exp[index] != ')') { if (exp[index] == ',') { index++; } else { Info next = f(exp, index);
if (judge == '&') { if (!next.ans) { ans = false; } } else { if (next.ans) { ans = true; } }
index = next.end + 1; } } }
info.ans = ans; info.end = index; }
return info;}
int main() { char* expression = "&(|(f))"; bool result = parseBoolExpr(expression);
printf("%d\n", result);
return 0;}
复制代码
评论