加载中…波兰式与逆波兰式
(2017-08-21 20:09:34)| 分类： 杂 |
一、波兰式
波兰式是在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之前，所以，这种表示法也称为前缀表达式。例如：3*（2-（5+1）），用波兰式来表示是：*
3 - 2 + 5 1。
阅读这个表达式需要从左至右读入表达式，如果一个操作符后面跟着两个操作数时，则计算，然后将结果作为操作数替换这个操作符和两个操作数，重复此步骤，直至所有操作符处理完毕。从左往右依次读取，直到遇到+
5 1，做计算后，将表达式替换为* 3 - 2 6，然后再次从左往右读取，直到遇到- 2 6，做计算后，将表达式替换为*3
（-4）（这里“-”为负号不是减号，-4为一个数负四），从而得到最终结果-12。
二、逆波兰式
逆波兰式（Reverse Polish
notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）。例如：3*（2-（5+1）），用逆波兰式来表示是：3
2 5 1 + - *，也就是把操作运算符往操作数后面放。
阅读这个表达式需要从左往右读入表达式，当读到第一个操作符时，从左边取出两个操作数做计算，然后将这个结果作为操作数替换这个操作符和两个操作数，重复此步骤，直至所有操作符处理完毕。
3 2 5 1 + - *
→3 2 6 - *
→3 （-4） *
→ -12
三、中缀表达式与波兰式、逆波兰式的转换
3*（2-（5+1））
波兰式
逆波兰式
→（3*（2-（5+1）））
→
→*（3-（2+（5 1）））
→ （3（2（5
1）+）-）*
→*
3 - 2 + 5 1
→
3
2 5 1 + - *
四、总结
喜欢
0
赠金笔