2011NOIP普及组真题 4. 表达式的值

embedded/2024/9/25 6:10:08/
线上OJ:

一本通::http://ybt.ssoier.cn:8088/problem_show.php?pid=1956

核心思想1:

1、本题考的是表达式树。完整的方法可以先建树,然后再计算的方式。
2、但是本题涉及的运算符并不多,故也可以用栈来直接模拟计算。符号放入符号栈,数值放入数值栈
3、本题要求的是最终结果为 0 的方案数,鉴于如下原则

如果是 c=a+b,仅当 a=0, b=0时, c=0。a和b只要有一个为1,则 c=1
如果是 c=a*b,仅当 a=1, b=1时, c=1。a和b只要有一个为0,则 c=0
故,若a[0]、b[0]表示各自节点数值为0的方案数;a[1]、b[1]表示各自节点数值为1的方案数

+号时:
c [ 0 ] = a [ 0 ] ∗ b [ 0 ] c[0] = a[0] * b[0] c[0]=a[0]b[0]
c [ 1 ] = a [ 1 ] ∗ b [ 0 ] + a [ 1 ] ∗ b [ 1 ] + a [ 0 ] ∗ b [ 1 ] c[1] = a[1]*b[0] + a[1]*b[1] +a[0]*b[1] c[1]=a[1]b[0]+a[1]b[1]+a[0]b[1]

*号时:
c [ 0 ] = a [ 0 ] ∗ b [ 0 ] + a [ 1 ] ∗ b [ 0 ] + a [ 0 ] ∗ b [ 1 ] c[0] = a[0] * b[0] + a[1]*b[0] + a[0]*b[1] c[0]=a[0]b[0]+a[1]b[0]+a[0]b[1]
c [ 1 ] = a [ 1 ] ∗ b [ 1 ] c[1] = a[1] * b[1] c[1]=a[1]b[1]

4、综上所述,数值节点存储的应该是数组 a[0], a[1], 分别表示当前节点为0的方案总数为1的方案总数

核心思想2:

对于每一个待入栈的符号 s[i]
1、如果是左括号,则直接入栈
2、如果是右括号,则把符号栈内的符号全部算完,直到遇到第一个左括号时停止。然后把第一个左括号弹出(右括号也不入栈,相当于抵消一对括号)
3、如果是运算符
3.1 如果栈为空,直接入栈
3.2 如果栈顶是左括号,直接入栈
3.3 如果栈顶符号优先级更低或相同,直接入栈
3.4 如果栈顶符号优先级高,则把栈顶高优先级的符号全部算完,直至遇到第一个优先级更低或相同停止。然后符号入栈
3.5 注意1:栈顶不会遇到右括号,因为右括号和左括号已经抵消了
3.6 注意2:本题不需要校验表达式的合法性,否则还需要考虑括号要匹配;第一个不能是右括号;最后一个不能是左括号
4、叶子节点的数值都存入 {1,1},因为叶子节点放0则为0,放1则为1,所以叶子节点值为0和1的总方案数都是1

题解代码:
#include <bits/stdc++.h>
#define MOD 10007
using namespace std;stack<char> op;
stack<vector<int>> num; // num[0]表示该节点为0的方案数;num[1]表示该节点为1的方案数int n;
string s;int pri[128];
void inipri()
{pri['+'] = 3; pri['*'] = 4;
}void cal()
{vector<int> a, b; // a, b为与 num 相同的结构 a = num.top();  // 数字栈取出第一个元素num.pop();      // 并弹出b = num.top();  // 数字栈取出第二个元素num.pop();      // 并弹出char c = op.top();  // 符号栈取出第一个运算符op.pop();       // 并弹出if(c == '+')  // 如果是+,则左右均为0的方案数的乘积为新的0的方案数;0*1+1*0+1*1为新的1的方案数num.push({(a[0] * b[0]) % MOD, (a[1]*b[1] + a[0]*b[1] + a[1]*b[0]) % MOD});else // 如果是*,则左右均为1的方案数的乘积为新的1的方案数;0*1+1*0+0*0为新的0的方案数num.push({(a[0]*b[0] + a[0]*b[1] + a[1]*b[0]) % MOD, (a[1] * b[1]) % MOD});
}int main()
{inipri(); // 初始化符号优先级cin >> n >> s;num.push({1, 1}); // 数字栈推的第一组数为 num[0]=1, num[1]=1。因为要么0,要么1,各有1种可能性for(int i = 0; i < n; i++){if(s[i] == '(')  op.push(s[i]); // 如果是左括号,则直接入符号栈else if(s[i] == ')')    // 如果是右括号(右括号的优先级最低){while( !op.empty() && op.top() != '(' )  cal(); // 则把符号栈内所有的运算符都算完,直到遇到第一个左括号op.pop(); // 然后弹出栈顶的左括号。这样就完成了一对括号之间的计算}else  // 如果读入的是*或者+{while( !op.empty() && pri[op.top()] > pri[s[i]] )  cal(); // 如果待入栈的符号优先级低于栈顶的符号,则把高优先级的运算符先计算op.push(s[i]);       // 符号加到栈中num.push({1, 1}); // 每次新增的叶子节点放 0和1的方案数都是 1}}while ( !op.empty() )  cal(); // 把所有运算符都计算完cout << num.top()[0]; // 最后一个结果的[0] 即表示为0的方案总数return 0;
}

http://www.ppmy.cn/embedded/33332.html

相关文章

使用FPGA实现串-并型乘法器

介绍 其实我们知道&#xff0c;用FPGA实现乘法器并不是一件很简单的事&#xff0c;而且在FPGA中也有乘法器的IP核可以直接调用&#xff0c;我这里完全就是为了熟悉一些FPGA的语法然后写了这样一个电路。 串-并型乘法器模块 从字面上看&#xff0c;串-并乘法器就是其中一个乘数…

《自动机理论、语言和计算导论》阅读笔记:p215-p351

《自动机理论、语言和计算导论》学习第 11 天&#xff0c;p215-p351总结&#xff0c;总计 37 页。 一、技术总结 1.constrained problem 2.Fermat’s lats theorem Fermat’s Last Theorem states that no three positive integers a, b and c satisfy the equation a^n b…

Linux基本命令

1. ls命令: 1&#xff09;ls-l :以长格式显示目录文件 例&#xff1a; 权限 链接文件所有者所有组文件大小文件最后修改日期文件关键 蓝色 → 目录 白色 → 普通文件 淡蓝色 → 链接文件 绿色 → 二进制可执行文件 红色 → 包文件或损坏文件 全绿色&…

微博完整逆向分析和数据抓取(最详细逆向实战教程,小白也能看懂)

大家好!我是爱摸鱼的小鸿,关注我,收看每期的编程干货。 逆向是爬虫工程师进阶必备技能,当我们遇到一个问题时可能会有多种解决途径,而如何做出最高效的抉择又需要经验的积累。本期文章将以抓取 微博 某个用户的推文数据为例,用实战的方式,带你详细地逆向分析微博 Cookie…

linux基本操作

vim的基本操作 正常模式&#xff1a;启动vim后默认处于正常模式。不论位于什么模式&#xff0c;按下Esc建都会进入正常模式。 插入模式&#xff1a;在正常模式中按下i&#xff0c;l&#xff0c;a&#xff0c;A等键&#xff0c;会进入插入模式。现在只用记住按i键会进行插入模…

华为OD试题之第k长子串

第k长子串 题目描述 给定一个字符串 只包含大写字母 求在包含同一字母的子串中 长度第K长的子串 相同字母只取最长的子串 输入描述 第一行 一个子串 1 < len < 100 只包含大写字母 第二行为k的值 输出描述 输出连续出现次数第k多的字母的次数 如果子串中只包含同一字母…

全能文件提取器,File Juicer for Mac,一键提取多媒体与文档内容!

File Juicer for Mac是一款专为Mac用户设计的文件内容提取工具。它拥有强大的功能&#xff0c;能够从各种文件中提取有用的信息和数据&#xff0c;包括但不限于图像、视频、音频和文本等。无论是常见的文件格式如PPT、PDF&#xff0c;还是一些难以打开或损坏的文件&#xff0c;…

Containerd方式部署K8s集群

1.1 Kubernetes基础环境部署 kubernetes有多种部署方式&#xff0c;目前主流的方式有kubeadm、minikube、二进制包 minikube&#xff1a;一个用于快速搭建单节点kubernetes的工具 kubeadm&#xff1a;一个用于快速搭建kubernetes集群的工具 二进制包 &#xff1a;从官网下载…