10 条题解
-
1
这道题是CSP-J的T3
我会详细的写出解题步骤,尽量让所有人看懂 题面我就不放出来了 那么这道题思路如下↓↓↓
第一步,把中缀表达式转换成后缀表达式
定义
中缀表达式就是正常人使用的表达式,包含括号、数字/变量和运算符,例如
(a+b)*(b-c)-(d-c)
而后缀表达式不需要括号先是数字/变量,遇到运算符后,取出前两个值计算,将计算结果重新存入算式,代替原来的两个数字/变量和运算符,将中缀表达式的例子转换后就是ab+bc-*dc--
需求
首先声明一个vector
sf
用来装后缀表达式,一个栈ops
用来缓存符号,一个字符串s
存输入的表达式 我们要让在同一个维度(括号)内,保持&
在栈的位置比|
高规则
- 优先级:
()
=1,&
=2,|
=3 - 如果是
0
或1
,直接输出到sf
中 - 如果是
(
,存入ops
- 如果是
)
,就将ops
中位于最近的(
之上的所有符号输出进sf
,再删除(
- 如果是
&
,就从栈顶输出优先级≤&
的逻辑运算符到sf
(只有&
)直到栈空或者遇到(
或者遇到|
- 如果是
|
,就从栈顶输出优先级≤|
的逻辑运算符到sf
(有&
和|
)直到栈空或者遇到(
注意,最后
ops
中还剩下一些运算符,要将其全部输出到sf
完成了转换部分,就要为后缀表达式建立表达式树
第二步,建立表达式树
我们需要声明一个结构体数组
tr
用于存放树的每个节点的值v
,左子树位置l
和右子树位置r
,声明一个栈sta
来缓存每个节点的位置所有叶子节点的值都为其对应的数字,用于计算 所有非叶子节点的值都为其对应运算符的值,也就是
&
=2,|
=3 所有叶子节点的左子树和右子树位置都为-1
因为叶子结点根本就没有左子树和右子树
第三步,dfs
我们通过dfs ~~~~(不会有人不知道深度优先搜索吧)~~~~来访问表达式树
dfs规则
- 叶子结点直接返回它的值
v
- 非叶子节点递归获取子树的值来计算
- 非叶子节点通过左子树判断是否出现短路,如果出现短路,直接返回左子树的值,跳过右子树
第四步,ACCODE
现在前三个部分的思路都清楚了,我们直接上代码:
以上是本蒟蒻的代码,希望您能看懂,如果有错,欢迎指出,有问题欢迎提问
- 优先级:
信息
- ID
- 2918
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 156
- 已通过
- 48
- 上传者