2023-07-19：布尔表达式 是计算结果不是 true 就是 false 的表达

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.主函数中定义了一个布尔表达式为"&(|(f))"，该表达式需要计算结果。

main

expression

2.调用函数，并将布尔表达式作为参数传递给它。

parseBoolExpr

3.函数中定义了一个内部递归函数，接收两个参数：表达式字符串和当前字符索引。

parseBoolExpr

f

exp

index

4.函数中首先获取当前索引处的字符，判断其类型。

f

judge

5.如果为't'，返回结果为true，索引保持不变。

judge

6.如果为'f'，返回结果为false，索引保持不变。

judge

7.如果为其他字符，进行进一步判断。

judge

8.如果为'!'，则递归调用函数，并将索引加1作为参数，获取递归调用的结果，对该结果执行逻辑非运算，返回结果为，索引更新为。

judge

f

next

!next.ans

next.end + 1

9.如果为'&'或'|'，则设置布尔变量为相应的值（true或false），并在循环中处理多个子表达式。

judge

ans

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完整代码如下：

packagemain
import(
"fmt"
)
typeInfostruct{
ansbool
endint
}
funcparseBoolExpr(expressionstring)bool{
returnf([]rune(expression),0).ans
}
funcf(exp[]rune,indexint)Info{
judge:=exp[index]
ifjudge=='f'{
returnInfo{false,index}
}elseifjudge=='t'{
returnInfo{true,index}
}else{
varansbool
index+=2
ifjudge=='!'{
next:=f(exp,index)
ans=!next.ans
index=next.end+1
}else{
ans=judge=='&'
forexp[index]!=')'{
ifexp[index]==','{
index++
}else{
next:=f(exp,index)
ifjudge=='&'{
if!next.ans{
ans=false
}
}else{
ifnext.ans{
ans=true
}
}
index=next.end+1
}
}
}
returnInfo{ans,index}
}
}
funcmain(){
expression:="&(|(f))"
result:=parseBoolExpr(expression)
fmt.Println(result)
}

rust代码如下：

fnmain(){
letexpression="&(|(f))";
letresult=parse_bool_expr(expression.to_string());
println!("{}",result);
}
fnparse_bool_expr(expression:String)->bool{
letexp:Vec=expression.chars().collect();
letinfo=f(&exp,0);
info.ans
}
structInfo{
ans:bool,
end:usize,
}
fnf(exp:&[char],index:usize)->Info{
letjudge=exp[index];
ifjudge=='f'{
returnInfo{
ans:false,
end:index,
};
}elseifjudge=='t'{
returnInfo{
ans:true,
end:index,
};
}else{
letmutans:bool;
letmutindex=index+2;
ifjudge=='!'{
letnext=f(exp,index);
ans=!next.ans;
index=next.end+1;
}else{
ans=judge=='&';
whileexp[index]!=')'{
ifexp[index]==','{
index+=1;
}else{
letnext=f(exp,index);
ifjudge=='&'{
if!next.ans{
ans=false;
}
}else{
ifnext.ans{
ans=true;
}
}
index=next.end+1;
}
}
}
Info{ans,end:index}
}
}

c++完整代码如下：

#include
#include
usingnamespacestd;
structInfo{
boolans;
//结束下标！
intend;
Info(boola,inte){
ans=a;
end=e;
}
};
Infof(conststring&exp,intindex){
charjudge=exp[index];
if(judge=='f'){
returnInfo(false,index);
}
elseif(judge=='t'){
returnInfo(true,index);
}
else{
//!
//&
//|
//再说！
boolans;
//!(?
//ii+1i+2
//&(?
//ii+1i+2
//|(?
//ii+1i+2
index+=2;
if(judge=='!'){
//!(?......)
//ii+1i+2
Infonext=f(exp,index);
ans=!next.ans;
index=next.end+1;
}
else{
//&
//i
//judge=='&'或者judge=='|'
ans=judge=='&';
while(exp[index]!=')'){
if(exp[index]==','){
index++;
}
else{
Infonext=f(exp,index);
if(judge=='&'){
if(!next.ans){
ans=false;
}
}
else{
if(next.ans){
ans=true;
}
}
index=next.end+1;
}
}
}
returnInfo(ans,index);
}
}
boolparseBoolExpr(conststring&expression){
returnf(expression,0).ans;
}
intmain(){
stringexpression="&(|(f))";
cout<return0;
}

c完整代码如下：

#include
#include
typedefstructInfo{
boolans;
intend;
}Info;
Infof(char*exp,intindex);
boolparseBoolExpr(char*expression){
returnf(expression,0).ans;
}
Infof(char*exp,intindex){
charjudge=exp[index];
Infoinfo;
if(judge=='f'){
info.ans=false;
info.end=index;
}
elseif(judge=='t'){
info.ans=true;
info.end=index;
}
else{
boolans;
index+=2;
if(judge=='!'){
Infonext=f(exp,index);
ans=!next.ans;
index=next.end+1;
}
else{
ans=judge=='&';
while(exp[index]!=')'){
if(exp[index]==','){
index++;
}
else{
Infonext=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;
}
returninfo;
}
intmain(){
char*expression="&(|(f))";
boolresult=parseBoolExpr(expression);
printf("%d\n",result);
return0;
}