海森的博客

Hacking, Cooking & Thinking

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

Posted on Edited on In Disqus:

Copyright 2019 HisenZhang

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

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

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

样例

输入样例 1

1
6 7 8 + *

输出样例 1

1
90

输入样例 2

1
2.2 3 * 4 +

输出样例 2

1
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()