AM - nahviss
前言
终于抽出时间更新了 QAQ
忘了今年哪场网络赛,有道Call of Accepted,通过人数很多,队友说去看看那个?我说不了不了,虽然我知道是水题,但是那个算法我不会啊!
终究欠的总是要还的 _(:з」∠)_
后缀表达式
https://blog.csdn.net/Antineutrino/article/details/6763722
https://liam0205.me/2016/12/14/Shunting-Yard-Algorithm/
https://blog.csdn.net/walkerkalr/article/details/22798365
表达式树
https://blog.csdn.net/buaa_shang/article/details/9124075
简单计算器 - HDU - 1237
思路
模板题(而且还没括号 = =||)
Call of Accepted - ACM-ICPC 2018 沈阳赛区网络预赛
题意
给定表达式求最大值与最小值,其中xdy表示可以取 [x, x * y] 中的数,并且d是右结合的,且运算优先级比 +-* 高
思路
需要对调度场算法进行改造
因为d是右结合的,故遇到栈顶为d时,不能立即将其弹出,而应继续入栈
剩下部分同调度场算法
最后是解决最大值最小值的问题,因为视作区间进行运算,'+'的范围则是小+小,大+大,'-'的范围是大-小,小-大,'*'的范围较难确定,但可以确定必然是端点之间乘出来的,所以枚举结果sort一下即可
Complicated Expressions - POJ - 1400
题意
对一个表达式,去除其冗余的括号
思路
先将其转为后缀表达式,再建表达式树,最后中序遍历输出
注意输出的时候判定是否需要加括号
① 如果中间的符号比其中一边的优先级大,那么该边需要加括号
② 如果中间的符号与右边的优先级相同,并且中间的符号为'/'或'-',那么需要加括号(因为没有结合律)
领取专属 10元无门槛券
私享最新 技术干货