Skip to content

Latest commit

 

History

History
96 lines (57 loc) · 3.91 KB

File metadata and controls

96 lines (57 loc) · 3.91 KB

English Version

题目描述

给定一个算术表达式的后缀表示法的标记(token) postfix ,构造并返回该表达式对应的二叉表达式树。

后缀表示法是一种将操作数写在运算符之前的表示法。例如,表达式 4*(5-(2+7)) 的后缀表示法表示为数组 postfix = ["4","5","7","2","+","-","*"] 。

抽象类 Node 需要用于实现二叉表达式树。我们将通过 evaluate 函数来测试返回的树是否能够解析树中的值。你不可以移除 Node 类,但你可以按需修改此类,也可以定义其他类来实现它。

二叉表达式树是一种表达算术表达式的二叉树。二叉表达式树中的每一个节点都有零个或两个子节点。 叶节点(有 0 个子节点的节点)表示操作数,非叶节点(有 2 个子节点的节点)表示运算符: '+' (加)、 '-' (减)、 '*' (乘)和 '/' (除)。

我们保证任何子树对应值的绝对值不超过 109 ,且所有操作都是有效的(即没有除以零的操作)

进阶: 你可以将表达式树设计得更模块化吗?例如,你的设计能够不修改现有的 evaluate 的实现就能支持更多的操作符吗?

 

示例 1:

输入: s = ["3","4","+","2","*","7","/"]
输出: 2
解释: 此表达式可解析为上述二叉树,其对应表达式为 ((3+4)*2)/7) = 14/7 = 2.

示例 2:

输入: s = ["4","5","7","2","+","-","*"]
输出: -16
解释: 此表达式可解析为上述二叉树,其对应表达式为 4*(5-(2+7)) = 4*(-4) = -16.

示例 3:

输入: s = ["4","2","+","3","5","1","-","*","+"]
输出: 18

示例 4:

输入: s = ["100","200","+","2","/","5","*","7","+"]
输出: 757

 

提示:

  • 1 <= s.length < 100
  • s.length 是奇数。
  • s 包含数字和字符 '+' 、 '-' 、 '*' 以及 '/' 。
  • 如果 s[i] 是数,则对应的整数不超过 105 。
  • s 保证是一个有效的表达式。
  • 结果值和所有过程值的绝对值均不超过 109 。
  • 保证表达式不包含除以零的操作。

解法

Python3

Java

...