【題目鏈接】

ybt 2006：【20CSPJ普及組】表達(dá)式
洛谷 P7073 [CSP-J2020] 表達(dá)式

【題目考點】

后綴表達(dá)式

表達(dá)式樹

通過后綴表達(dá)式建立表達(dá)式樹：

• 遍歷后綴表達(dá)式字符串：
  • 若讀取到數(shù)字，生成結(jié)點，入棧
  • 若讀取到運算符，生成運算符結(jié)點，出棧兩個結(jié)點，分別作為運算符結(jié)點的左右孩子，將運算符結(jié)點入棧
• 最后棧頂結(jié)點就是表達(dá)式樹的根結(jié)點

【解題思路】

• 題中求的是布爾表達(dá)式，問改變某個變量的值后，整個式子的值是否變化。
  由此可知，我們需要求出一個布爾型的數(shù)組isChange
  • isChange[i]為真，表示第i個變量變化后，表達(dá)式的值會變化。
  • isChange[i]為假時，表示第i個變量變化后，表達(dá)式的值不會變化。
• 考察表達(dá)式a|b，當(dāng)a為0，b為1時，0|1結(jié)果為0。此時如果a發(fā)生改變，式子變?yōu)?|1，結(jié)果為1。如果b發(fā)生改變，式子變?yōu)?|0結(jié)果為0。說明a的改變可以改變表達(dá)式的值，而b的改變不會改變表達(dá)式的值。
  由于運算數(shù)只有0、1，運算符只有&、|，可以枚舉不同的表達(dá)式中改變兩個變量后能否改變表達(dá)式的值，將這些情況保存起來，設(shè)為兩個數(shù)組isChAnd和isChOr。
  • isChAnd[a][b][c]: 在a&b這一表達(dá)式中，a(c為0)或b(c為1)的值變化能否影響運算的結(jié)果。
  • isChOr[a][b][c]: 在a|b這一表達(dá)式中，a(c為0)或b(c為1)的值變化能否影響運算的結(jié)果。
• 通過后綴表達(dá)式建立表達(dá)式樹
  • 葉子結(jié)點記錄變量編號(x)，變量值(val)
  • 每個子樹都是一個表達(dá)式。分支結(jié)點記錄以該結(jié)點為根的子樹所表示的表達(dá)式的值(val)、該結(jié)點的值如果變化對父結(jié)點的值是否有影響(inf)。
• 判斷哪些變量變化會對整體表達(dá)式的值有影響，構(gòu)造isChange數(shù)組
  • 如果一個結(jié)點的變化對其父結(jié)點沒有影響，那么該結(jié)點所有孩子結(jié)點的變化對父結(jié)點都沒有影響。即以該結(jié)點為根結(jié)點的子樹的葉子結(jié)點對應(yīng)的變量的變化對整體表達(dá)式的值沒有影響。
  • 遍歷表達(dá)式樹，如果遇到自身值變化不會影響父結(jié)點的結(jié)點，那么，就不再向下遍歷。以此方法，遍歷到的所有葉子結(jié)點對應(yīng)的變量，其變化都會影響整體表達(dá)式的值，對應(yīng)地設(shè)置isChange數(shù)組。
• 根據(jù)題目需要，查詢isChange數(shù)組，輸出結(jié)果。

【題解代碼】

解法1：

#include <bits/stdc++.h> using namespace std; #define N 1000005 typedef struct Node//表達(dá)式樹結(jié)點 {int left, right;bool val;//值bool inf;//本節(jié)點值的改變是否能影響父結(jié)點int x;//該結(jié)點的變量編號 }Node; bool val[N];//val[i]:變量x[i]的初值 char s[N];//讀入的字符串 Node node[N];//結(jié)點池 int ni = 1;//結(jié)點池下標(biāo) bool isChange[N];//isChange[i] 第i個變量變化后，能否影響最終結(jié)果 //isChAnd[a][b][c]: 當(dāng)?shù)?個數(shù)的值是a，第2個數(shù)值是b時，第c+1個數(shù)的值變化能否影響運算的結(jié)果。 //例:0&0 = 0 第一個數(shù)0變?yōu)?，公式變?yōu)?&0 = 0，不能影響運算結(jié)果。那么有isChAnd[0][0][0] = false; bool isChAnd[2][2][2], isChOr[2][2][2]; //初始化isChAnd和isChOr void initIsCh() {isChAnd[0][0][0] = 0; isChAnd[0][0][1] = 0;isChAnd[0][1][0] = 1; isChAnd[0][1][1] = 0;isChAnd[1][0][0] = 0; isChAnd[1][0][1] = 1;isChAnd[1][1][0] = 1; isChAnd[1][1][1] = 1;isChOr[0][0][0] = 1; isChOr[0][0][1] = 1;isChOr[0][1][0] = 0; isChOr[0][1][1] = 1;isChOr[1][0][0] = 1; isChOr[1][0][1] = 0;isChOr[1][1][0] = 0; isChOr[1][1][1] = 0; } //生成表達(dá)式樹，返回根節(jié)點的地址 int initTree() {stack<int> stk;//存放結(jié)點地址int xNum = 0, np, lp, rp;//xNum:變量編號 np:新結(jié)點地址 lp，rp：左右孩子地址 char cal;//運算符int len = strlen(s);for(int i = 0; i <= len; ++i){if(s[i] >= '0' && s[i] <= '9')xNum = xNum * 10 + s[i] - '0';else if(s[i] == '&' || s[i] == '|' || s[i] == '!')cal = s[i];else if(s[i] == ' ' || s[i] == '\0'){if(xNum > 0)//提取出x{np = ni++; node[np].val = val[xNum];node[np].x = xNum;stk.push(np);xNum = 0;}else//提取出運算符{np = ni++;if(cal == '!'){lp = stk.top();stk.pop();node[lp].inf = true;//取非運算的運算數(shù)的改變會影響表達(dá)式的值node[np].val = !node[lp].val;node[np].left = lp;}else{rp = stk.top();stk.pop();lp = stk.top();stk.pop();node[np].left = lp;node[np].right = rp;if(cal == '&'){node[np].val = node[lp].val && node[rp].val;node[lp].inf = isChAnd[node[lp].val][node[rp].val][0];node[rp].inf = isChAnd[node[lp].val][node[rp].val][1];}else if(cal == '|'){node[np].val = node[lp].val || node[rp].val;node[lp].inf = isChOr[node[lp].val][node[rp].val][0];node[rp].inf = isChOr[node[lp].val][node[rp].val][1];}}stk.push(np);}}}return stk.top(); } //設(shè)置isChange數(shù)組 遍歷表達(dá)式樹 void initIsChange(int p) {if(node[p].inf)//如果該點值的變化不能影響父結(jié)點 ，就不遍歷了。{if(node[p].left == 0 && node[p].right == 0){isChange[node[p].x] = true;//如果遍歷到葉子結(jié)點，那么設(shè)置該變量的變化可以影響表達(dá)式的值}else{if(node[p].left != 0)initIsChange(node[p].left);if(node[p].right != 0)initIsChange(node[p].right);}} }int main() {initIsCh();int n, q, qi;bool res;//正常計算的結(jié)果cin.getline(s, N);scanf("%d", &n);for(int i = 1; i <= n; ++i)//輸入各個變量的值scanf("%d", &val[i]);int root = initTree();//生成表達(dá)式樹res = node[root].val;//通過已有變量值求出的表達(dá)式的原始結(jié)果node[root].inf = true;//為了配合下面的函數(shù)，必須設(shè)這一點initIsChange(root);//設(shè)置isChange數(shù)組scanf("%d", &q);//輸入查詢組數(shù)for(int i = 1; i <= q; ++i){scanf("%d", &qi);//改變第qi變量if(isChange[qi])//如果第qi變量的改變能引起表達(dá)式值的變化printf("%d\n", !res);//輸出變化后的結(jié)果elseprintf("%d\n", res);//輸出原結(jié)果}return 0; }

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通 2006：【20CSPJ普及组】表达式 | 洛谷 P7073 [CSP-J2020] 表达式的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。