挑战 | 逆波兰表达式解释器

Copyright 2019 HisenZhang

1920年, 逆波兰表示法Reverse Polish Notation首次被提出. 不同于我们常用的中置表达式, 逆波兰表示法将操作符写在操作数后面, 例如阶乘!.

逆波兰表示法的这一特性适合使用栈stack来解析. 这种设计可以减少存储器访问. 因此在1960和1970年代, 逆波兰记法广泛应用于台式和手持计算器.

在这个挑战里, 你需要编写一个解释器来计算逆波兰表达式, 实现加减乘除四则运算.

样例

输入样例 1

6 7 8 + *

输出样例 1

90

输入样例 2

2.2 3 * 4 +

输出样例 2

10.6

完成度

本挑战的完成度分为两个等级

1. 可以解析个位数的操作数
2. 可以解析多位操作数(包括浮点数)

目标

1. 学习栈stack结构与栈的操作
2. 强化列表与字符串的操作
3. 强化四则运算的编程
4. 强化条件/循环语句

材料

访问OneDrive以获取相关材料

1. 中文维基百科:
   • reverse_polish_notation.pdf
2. 视频 & 英语字幕:
   • Reverse Polish Notation and The Stack - Computerphile.m4v
   • Reverse Polish Notation and The Stack - Computerphile.ass
3. 从零开始学Python(第二版)节选
   • list_functions.pdf

提示

1. 列表对象有两个方法:
   • append()
   • pop()
2. 字符串对象有个方法:
   • strip()