1384 : 波兰式,逆波兰式
- 时间限制Time Limit
- 1 秒Sec
- 内存限制Memory Limit
- 128 兆MB
- 提交次数Submitted
- 147 次Times
- 通过次数Solved
- 36 次Times
标准评测 Standard
从标准输入读入,结果写到标准输出。评测将输出拆成 token,与标准答案逐项比较,不按整段逐字节比对。
Read from standard input and write to standard output. The judge splits the output into tokens and compares them with the official answer; it does not compare raw bytes.
| 比对Compare | token 相同即通过。中间的空格、制表符、换行可多可少。Matching tokens pass. Extra spaces, tabs, or newlines between them are ignored. |
|---|---|
| 不同则错Differs | token 个数或内容不同即错误。23 与 2 3、02 与 2、2.0 与 2 均视为不同。A different token count or value is wrong. 23 vs 2 3, 02 vs 2, and 2.0 vs 2 all differ. |
| 输入Input | 标准输入,格式见题面。Standard input; format as in the statement. |
| 输出Output | 标准输出。Standard output. |
| 时间与内存Time and memory | 记这一份程序的 CPU 时间和内存峰值。题目上的时间限制、内存限制就是这一份的上限。The record is this program’s CPU time and peak memory. The limits on the problem apply to this one run. |
题目描述Description
表达式有三种表示方法,分别为:
- 前缀表示(波兰式):运算符+操作数1+操作数2
- 中缀表示:操作数1+运算符+操作数2
- 后缀表示(逆波兰式):操作数1+操作数2+运算符
例如:a +b * (c -d ) - e/f
- 波兰式:
-+a*b-cd/ef(运算符在操作数的前面,用递归计算波兰式) - 中缀式:
a+b*c-d-e/f
- 逆波兰式:
abcd-*+ef/-(运算符在操作数的后面,用栈计算逆波兰式)
中缀表示就是原表达式去掉括号。
根据表达式求波兰式、逆波兰式都是教材第三章表达式求值的思想。
求波兰式,需要操作数栈(注意不是计算结果入栈,计算式入栈),运算符栈。区别在于从后往前扫描表达式,(
换成
)。栈顶运算符优先级>新读入运算符优先级出栈,教材第三章表3.1中的相同运算符优先级>(从左往右计算)改为<,例如栈顶为+,新读入的为+,则栈顶优先级<新读入的优先级。
求逆波兰式,只需要运算符栈。操作数直接输出,操作符按表3.1优先级顺序出栈,输出。
输入表达式,求其波兰式和逆波兰式。
输入格式Input
测试次数
每组测试数据一行,一个100字符以内的合法表达式。
输出格式Output
对每组测试数据,输出两行
第一行,表达式的波兰表示
第二行,表达式的逆波兰表示
不同组测试数据间以空行分隔。
样例Sample
出题Author
CSGrandeur
来源Source
算法竞赛入门-栈
题目到此结束End of problem