Skip to content

Latest commit

 

History

History

1628.Design an Expression Tree With Evaluate Function

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

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

...