将中缀表达式(带括号)转换为二叉树 [英] Converting an infix expression (with parentheses) into a binary tree

问题描述

作为Java分配的一部分，我必须采用输入算术表达式并将其存储在二进制树中.

As part of a Java assignment, I have to take an input arithmetic expression and store it in a binary tree.

除了读取表达式的字符串并将其存储在二叉树中的那部分外，我已经完成了分配所需的一切.

I have done everything necessary for the assignment except for the part where I read in the string of the expression and store it in the binary tree.

我创建了一个名为BinaryTree的类.它的唯一字段是一个称为root的treenode.该treenode在BinaryTree中定义为内部类.它具有3个字段，一个通用数据字段和两个BinaryTree类型的子代(左和右).

I have created a class called BinaryTree. Its only field is a treenode called root. This treenode is defined as an innerclass in BinaryTree. It has 3 fields, a generic data field, and two children (left and right) that are type BinaryTree.

我很难定义一个算法来读取诸如

I'm having a very difficult time defining an algorithm for reading in an expression such as

(5 *(2 + 3)^ 3)/2

(5*(2+3)^3)/2

并将其存储在这样的树中

and storing it in a tree like this

             /
        ^          2
    *       3
  5   +
     2  3

任何人都可以提供有关该算法的帮助吗?

Can anyone help with the algorithm?

推荐答案

看看分流码算法.来自维基百科:

在计算机科学中，调车场算法是一种解析以中缀符号指定的数学表达式的方法.它可用于产生反向波兰表示法(RPN)或抽象语法树(AST)的输出.该算法由Edsger Dijkstra发明，并命名为调车场"算法，因为其操作类似于铁路调车场. Dijkstra首先在Mathematisch Centrum报告MR 34/61中描述了调车场算法.

In computer science, the shunting-yard algorithm is a method for parsing mathematical expressions specified in infix notation. It can be used to produce output in Reverse Polish notation (RPN) or as an abstract syntax tree (AST). The algorithm was invented by Edsger Dijkstra and named the "shunting yard" algorithm because its operation resembles that of a railroad shunting yard. Dijkstra first described the Shunting Yard Algorithm in Mathematisch Centrum report MR 34/61.

这篇关于将中缀表达式(带括号)转换为二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！