刷题记 III-III

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

题意

对一个表达式,去除其冗余的括号

思路

先将其转为后缀表达式,再建表达式树,最后中序遍历输出

注意输出的时候判定是否需要加括号

① 如果中间的符号比其中一边的优先级大,那么该边需要加括号

② 如果中间的符号与右边的优先级相同,并且中间的符号为'/'或'-',那么需要加括号(因为没有结合律)

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180924G1GVMV00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券