1

How do you, given any string expression, populate a tree?

I have an assignment that I am stuck on.

I need to evaluate the following expression (( 5 * 10 ) /2 - (( 2 + 3) + 6)) using any data structure.

Using a stack, I am able to verify that the string is well formed. But how can I add the various values into a tree and then evaluate them in order.

Please give me any hints you may have on how I can read the string ((( 490 * 9 ) / 2)/5/6 - (( 2/4 + 3) + 6 * 5))

For instance, How do I get the (-) to be the root of the three when it is the 15th substring in the input expression? How do I make sure that the (/)6 expression happens after (/)5 etc.

4

5 回答 5

3

您正在寻找的内容在这里提供：http: //www.codeproject.com/Articles/88435/Simple-Guide-to-Mathematical-Expression-Parsing

于 2012-05-17T20:28:19.383 回答
2

评估任何字符串 [表示数学] 表达式

你需要做三件事：

  • 为代表您的语言的抽象语法树定义一个类型
  • 为您的语法编写递归下降解析器
  • 为你的语法写一个解释器

你可以很容易地做到这一点。

我将使用 Haskell 表示法，因为它很简洁，但如果你愿意，你可以翻译它。

适合您语言的类型：

data Exp = Op BinOp Exp Exp
         | Lit Int

data BinOp = Plus
           | Times
           | Div
           | Sub

现在，我们可以为这种语言的表达式编写一个解释器：

eval :: Exp -> Int
eval (Lit n)      = n
eval (Op o e1 e2) = 
   let v1 = eval e1
       v2 = eval e2
   in case o of
       Plus  -> v1 + v2
       Times -> v1 * v2
       Sub   -> v1 - v2
       Div   -> v1 / v2 -- note, may fail!

好的。这就是您的语言中术语的评估器。现在写一个递归下降解析器......

于 2012-05-17T22:57:59.173 回答
1

这里的其他答案包括将表达式树读入内存，但它们不包括在构建树后评估树。

评估树的一般策略是树应该由节点和叶子组成，其中节点是有孩子的运算符，叶子是常数值。例如，表达式 (((490 * 9) / 2) / 5 / 6 - ((2 / 4 + 3) + 6 * 5)) 转换为树

                      -
                  / \
                 / \
              div +
             / \ / \
          格 6 + *
         / \ / \ / \
      分区 5 分区 3 6 5
     / \ / \
    * 2 2 4
  / \
450 9

要评估这棵树，请从根开始。您首先递归地评估左子树和右子树，然后将运算符应用于两个子树评估的结果。每个叶子（数字）都对自己进行评估。

在这种情况下，您将从根 (-) 开始，将左子树评估为 73.5，将右子树评估为 33.5，然后减去得到最终结果 40。

作为一个更精确的例子，让我们看看在进行了几层递归调用之后，树最左边的节点。叶 450 计算为 450，叶 9 计算为 9，节点(* 450 9)（以类似 Lisp 的前缀表示法编写树的节点）计算为 4050。因此，从节点 开始(/ (* 450 9) 2)，左递归调用计算为 4050，而右递归调用计算为 4050递归调用的计算结果为 2，这意味着整个节点的计算结果为 2025。只要在组合值之前从节点进行递归调用，并确保每个叶子都对自身进行计算，树的计算就很简单了。

于 2012-05-17T20:58:59.057 回答
1

编辑第二个：操作澄清，查看其他答案

于 2012-05-17T20:32:56.733 回答
1

括号表示操作的顺序，因此类似于您使用堆栈来确保所有匹配的内容，您可以解析出这些匹配项并将它们用作树中的元素来创建用于评估的层次结构，其中运算符是每个宽度的子级 -括号匹配的明智级别。

于 2012-05-17T20:30:08.633 回答