|
|
本帖最后由 tiger 于 2023-8-25 20:38 编辑
今天我们来探讨一下表达式的求值，我们的内容分为三部分：
1.认识表达式
2.表达式计算
3.例题
===================================================
===================================================
Ⅰ.认识表达式
喲！康康谁来辣！（出自《信息学基地.oj》------Famer Lei 我没侵权吧）
哦，是我们今天的主角------Mr.表达式先生
表达式分为三种：前缀表达式，中缀表达式，后缀表达式
大家喜欢哪种呢?投个票吧！
不不不不不不，很简单，人类喜欢中缀表达式，比如：
1.993*10^18/123^2.28
计算机喜欢前缀和后缀表达式：
*^/^1.993 10 18 123 2.28
1.993 10 18 123 2.28*^/^
表达式还可以抽象成表达式树
前缀表达式是前序遍历的另一种具象的体现，
中缀表达式是中序遍历的另一种具象的体现，
后缀表达式是后序遍历的另一种具象的体现
===================================================
===================================================
Ⅱ.表达式计算
很简单，前缀表达式从右至左扫描
后缀表达式从左至右扫描
中缀不用说了
===================================================
===================================================
Ⅲ.例题
1349就不说了oj.singera.cn/dist/quesInfo?problem_id=1349
2122小编tiger都没做对oj.singera.cn/dist/quesInfo?problem_id=2122
3638最适合不过了
思路一：
∣s∣=1 有 2 22 种情况：1 11, 0 00
∣ s ∣ = 3 |s|=3∣s∣=3 有 8 88 种情况：1 & 0 1\&01&0、0 & 1 0\&10&1、1 & 1 1\&11&1、0 & 0 0\&00&0、0 ∣ 1 0|10∣1、1 ∣ 1 1|11∣1、1 ∣ 0 1|01∣0、0 ∣ 0 0|00∣0
∣ s ∣ = 5 |s|=5∣s∣=5 时，如果有括号则和 ∣ s ∣ = 3 |s|=3∣s∣=3的情况是一样的，没有括号共有 32 3232 种情况。
可打表或if语句实现，可得 20 分。
详见【CSP2022J-T3】逻辑表达式_2022-csp-j-3-逻辑表达式_sqtiger的博客-CSDN博客
思路二：
if语句，考虑没有括号的情况：
- #include <bits/stdc++.h>
- using namespace std;
- string s;
- int ans1 = 0, ans = 0;
- int main(){
- cin >> s;
- bool f = false, f1 = true;
- for (int i = 0; i < s.size(); ++i){
- if (s[i] == '1' || s[i] == '0'){
- f1 = f1 && (s[i] - '0');
- } else if (s[i] == '|'){
- f = f || f1;
- if (f) ans++;
- f1 = true;
- } else {
- if (!f1 && !f) ans1++;
- }
- }
- f = f || f1;
- cout << f << endl;
- cout << ans1 << " " << ans << endl;
- return 0;
- }
思路三：
用栈跑一个括号匹配，用 vh 来表示标号为 i 的左括号匹配的右括号的位置。
递归求解，dfs(l, r)求区间 [l, r] 内表达式的值。
每个区间记录三个值，1、布尔表达式的值v；2、& \&& 短路的次数 s1；3、∣ |∣ 短路的次数s2.
递归时具体操作
ans用来记录整个区间的值
ans1 用来记录当前& \&&分段的值.
tmp 用来记录当前操作数的值
读到 0 00、1 11、( ((字符，则计算当前操作数。
读到 & \&& 字符，ans1.v值为false，则发生 & \&& 短路，ans1.s1++；否则，将 tmp 值累加到 ans1上。
读到 ∣ |∣ 字符，先像上面将操作数 tmp 累计到 ans1 上；ans.v的值为true，则发生一次 ∣ |∣ 短路，ans.s2++；否则，将 ans1 值累加到 ans 上。
时间复杂度：O ( n ) O(n)O(n)，可得100分。
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 2E6 + 10;
- struct nod{
- bool v;
- int s1, s2;
- nod(bool _v, int _s1, int _s2): v(_v), s1(_s1), s2(_s2){}
- };
- string s;
- int vh[MAXN];
- void readp(){
- cin >> s;
- stack<int>stk;
- for (int i = 0; i < s.size(); ++i){
- if (s == '(')
- stk.push(i);
- else if (s == ')'){
- vh[stk.top()] = i;
- stk.pop();
- }
- }
- }
- void cal(nod &a, nod b, char op){
- if (op == '&')
- a = nod(a.v && b.v, a.s1 + b.s1, a.s2 + b.s2);
- else
- a = nod(a.v || b.v, a.s1 + b.s1, a.s2 + b.s2);
- }
- nod dfs(int l, int r){
- if (s[l] == '(' && vh[l] == r) return dfs(l + 1, r - 1);;
- nod ans = nod(false, 0, 0), ans1 = nod(true, 0, 0), tmp = nod(true, 0, 0);
- for (int i = l; i <= r; ++i){
- if (s == '1' || s == '0')
- tmp = nod(s - '0', 0, 0);
- else if (s == '(')
- tmp = dfs(i + 1, vh - 1), i = vh;
- else if (s == '|'){
- if (ans1.v) cal(ans1, tmp, '&');
- else ans1.s1++;
- if (!ans.v) cal(ans, ans1, '|');
- else ans.s2++;
- ans1 = nod(true, 0, 0);
- }
- else if (ans1.v) {
- cal(ans1, tmp, '&');
- } else ans1.s1++;
- }
- //处理最后一个操作数
- if (ans1.v) cal(ans1, tmp, '&');
- else ans1.s1++;
- //处理最后一段
- if (!ans.v) cal(ans, ans1, '|');
- else ans.s2++;
- return ans;
- }
- int main(){
- readp();
- nod sol = dfs(0, s.size() - 1);
- cout << sol.v << endl;
- cout << sol.s1 << " " << sol.s2 << endl;
- return 0;
- }
其他思路欢迎发至邮箱：tiger201303@163.com
今天的内容到此结束
大家下次再见!!!
彩蛋(Willim)
bbs.singera.cn/forum.php?mod=viewthread&tid=370&extra=page%3D1
bbs.singera.cn/forum.php?mod=viewthread&tid=371&extra=page%3D1
|
|
发表于 2023-8-25 20:36:02
置顶卡