The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

Reverse Polish Notation-我的原创题目

Reverse Polish Notation


Time Limit: Nolimit


 


Memory Limit: 65536K



Description


标准的表达式如"A+B",在数学上学名叫中缀表达式(Infix Notation),原因是运算符号在两个运算对象的中间。相对应的还有前缀表达式(Prefix Notation),如:"+ - A * B C D",转换成中缀表达式为:"A - B * C + D";后缀表达式(Postfix Notation),比如前所述的中缀表达式转换为后缀表达式为:"A B C * - D +"。为了纪念波兰数学家鲁卡谢维奇(Jan Lukasiewicz),前缀表达式被称作波兰表达式,后缀表达式称为逆波兰表达式(Reverse Polish Notation)。
后缀表达式的优点是显而易见的,编译器在处理时候按照从左至右的顺序读取逆波兰表达式,遇到运算对象直接压入堆栈,遇到运算符就从堆栈提取后进的两个对象进行计算,这个过程正好符合了计算机计算的原理。
后缀表达式比前缀表达式更加易于转换,并且它的最左面一定为数字,这一点在实际编程的时候就会体会到它的好处了。
逆波兰表达式有一个更大的优点,就是拆括号,根据运算符的级别将中缀表达式转换成逆波兰表达式后,运算顺序就已经替代了运算符的级别,这样也避免了括号提高运算级别的特殊处理。
事实上,人的思维方式很容易固定~~!正如习惯拉10进制。就对2,3,4,8,16等进制不知所措一样~~!人们习惯的运算方式是中缀表达式。而碰到前缀,后缀方式。。迷茫其实仅仅是一种表达式子的方式而已(不被你习惯的方式)我这里教你一种也许你老师都没跟你讲的简单转换方式一个中缀式到其他式子的转换方法~~这里我给出一个中缀表达式~a+b*c-(d+e)
第一步:按照运算符的优先级对所有的运算单位加括号
~
        式子变成拉:
((a+(b*c))-(d+e))
第二步:转换中缀与后缀表达式

        后缀:把运算符号移动到对应的括号后面
        则变成拉:((a(bc)*)+(de)+)-
        把括号去掉:abc*+de+-  后缀式子出现

发现没有,前缀式,后缀式是不需要用括号来进行优先级的确定的。
现在,你需要用计算机来实现这一过程,怎么样,是否有兴趣一试呢?如果答案是肯定的话,Let‘s go!

 


Input


按照人们日常的输入习惯,请输入一个带浮点型带括号的中缀表达式(不需要添加等号)。


输入的算式可以包含整数,小数,+,-,*,/,(,)这几种类型,


当然,为了体现和谐社会的客观要求及人文关怀,你可以假设这个算式的总字符长度小于100字节。


Output


输出与此中缀表达式对应的逆波兰表达式,为了区分数字,请将数字与数字或字符与字符以空格隔开。


最后一个字符后不需要添加空格,各组测试数据之间请用空行隔开。(输出到文件尾)


Sample Input


1.5+2.5*3-4+5


1*2+3/4


Sample Output


1.5 2.5 3 * + 4 5 + -

 


 


1 2 3 + * 4 /


Source


Weitao(伟涛) 's first submitting problem for njust ACM team;

 

posted on 2009-02-19 13:02 abilitytao 阅读(1086) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理