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