2023-07-19：布爾表達(dá)式 是計算結(jié)果不是 true 就是 false 的表達(dá)式 有效的表達(dá)式需遵
2023-07-19：布爾表達(dá)式 是計算結(jié)果不是 true 就是 false 的表達(dá)式
有效的表達(dá)式需遵循以下約定：
't'，運算結(jié)果為 true
'f'，運算結(jié)果為 false
'!(subExpr)'，運算過程為對內(nèi)部表達(dá)式 subExpr 進行 邏輯非（NOT）運算
'&(subExpr1, subExpr2, ..., subExprn)'
運算過程為對 2 個或以上內(nèi)部表達(dá)式
subExpr1, subExpr2, ..., subExprn 進行 邏輯與（AND）運算
'|(subExpr1, subExpr2, ..., subExprn)'
運算過程為對 2 個或以上內(nèi)部表達(dá)式
subExpr1, subExpr2, ..., subExprn 進行 邏輯或（OR）運算
給你一個以字符串形式表述的 布爾表達(dá)式 expression，返回該式的運算結(jié)果。
題目測試用例所給出的表達(dá)式均為有效的布爾表達(dá)式，遵循上述約定。
輸入：expression = "&(|(f))"。
輸出：false。
答案2023-07-19：
大體過程如下：
1.主函數(shù)main中定義了一個布爾表達(dá)式expression為"&(|(f))"，該表達(dá)式需要計算結(jié)果。
2.調(diào)用parseBoolExpr函數(shù)，并將布爾表達(dá)式作為參數(shù)傳遞給它。
3.parseBoolExpr函數(shù)中定義了一個內(nèi)部遞歸函數(shù)f，接收兩個參數(shù)：表達(dá)式字符串exp和當(dāng)前字符索引index。
4.函數(shù)f中首先獲取當(dāng)前索引處的字符judge，判斷其類型。
5.如果judge為't'，返回結(jié)果為true，索引保持不變。
6.如果judge為'f'，返回結(jié)果為false，索引保持不變。
7.如果judge為其他字符，進行進一步判斷。
8.如果judge為'!'，則遞歸調(diào)用f函數(shù)，并將索引加1作為參數(shù)，獲取遞歸調(diào)用的結(jié)果next，對該結(jié)果執(zhí)行邏輯非運算，返回結(jié)果為!next.ans，索引更新為next.end + 1。
9.如果judge為'&'或'|'，則設(shè)置布爾變量ans為相應(yīng)的值（true或false），并在循環(huán)中處理多個子表達(dá)式。
10.在循環(huán)中，當(dāng)當(dāng)前字符不是')'時，執(zhí)行以下操作：
-?如果當(dāng)前字符是','，則將索引加1，跳過逗號字符。
-?否則，遞歸調(diào)用`f`函數(shù)，并將當(dāng)前索引作為參數(shù)獲取遞歸結(jié)果`next`。
-?根據(jù)父表達(dá)式的運算符進行相應(yīng)的邏輯運算，更新布爾變量`ans`的值。
-?更新索引為`next.end?+?1`。
11.循環(huán)結(jié)束后，返回結(jié)果為Info{ans, index}，其中ans為布爾表達(dá)式的計算結(jié)果，index為當(dāng)前索引。
12.返回到parseBoolExpr函數(shù)，獲取f函數(shù)的結(jié)果Info，返回Info.ans作為布爾表達(dá)式的最終計算結(jié)果。
13.輸出最終結(jié)果。根據(jù)給定的表達(dá)式"&(|(f))"，計算結(jié)果為false，打印結(jié)果false。
時間復(fù)雜度：假設(shè)表達(dá)式字符串的長度為n，遞歸過程涉及到遍歷字符串中的每個字符，因此時間復(fù)雜度為O(n)。
空間復(fù)雜度：遞歸調(diào)用過程中會使用額外的?？臻g來保存遞歸的狀態(tài)，最壞情況下遞歸的深度可以達(dá)到n，因此空間復(fù)雜度為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++完整代碼如下：
using?namespace?std;
struct?Info?{
????bool?ans;
????//?結(jié)束下標(biāo)！
????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完整代碼如下：
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;
}
