生成表示前缀表达式的树的算法

Question

我正在开发一个java程序，用于计算算术前缀表达式。它采用用户将输入的普通算术表达式，然后将其转换为前缀形式。例如，如果输入以下表达式：3+(5+9(*2，它会将其转换为：+3*+592。然后将其存储在表达式树中，在此处输入图像描述。我正在寻找一种算法来正确地将前缀表达式存储在树中我使用一个具有char值的节点和两个Nodes作为类属性我已经完成了所有的工作来评估表达式(使用树(，我只需要将前缀表达式存储在树中。如果您对java实现有任何建议，它会更好。感谢

节点类别：

public class Noeud
{
String value;
static Noeud right;
static Noeud left;
// Constructors
public Noeud()
{
this.value = "";
this.right = this.left = null;
}
public Noeud(String operation)
{
this.value = operation;
this.right = this.left = null;
}

public Noeud(String operation, Noeud filsdroit, Noeud filsgauche)
{
this.value = operation;
this.right = filsdroit;
this.left  = filsgauche;
}
// Methods
public void ajouteGauche(String caractere) // to add the left child
{
Noeud gauche = new Noeud(caractere);
this.left = gauche; 
}
public void ajouteDroite(String caractere) // to add the right child
{
Noeud droite = new Noeud(caractere);
this.right = droite;
}

public boolean isLeaf()
{
return this.right == null && this.left == null;
}
// toString
}

这就是我的程序要做的：

public static void main(String[] args)
{
System.out.println("Input a infix arithmetic expression");
Scanner scan = new Scanner(System.in);
String expInitiale = scan.nextLine();
expInitiale = infixToPreFix(expInitiale).toString();
System.out.println("Votre expression en forme préfixe " + expInitiale);
/* Building the tree (That's what i need) */
Noeud root = constructTree(expInitiale);
// Evaluation of the expression
double result = eval(root);
System.out.prinln("The result is" + result );
}
}

Answer 1

实际上，您从左到右解析字符串：

public class Parser {
private final String prefix;
int pos = 0;
public Parser(String prefix) {
this.prefix = prefix;
}
public Noeud parse() {
char c = prefix.charAt(pos);
pos++;
String token = Character.toString(c);
if (Character.isDigit(c)) {
return new Noeud(token);
}
return new Noeud(token, parse(), parse());
}
}

读取节点的基本算法是：

• 读取一个字符(下一个标记(
• 如果该字符是一个数字，则返回一个新的叶节点
• 否则，再读取两个节点，并用它们作为左子节点和右子节点构造一个新节点

您的constructTree功能如下：

public static Noeud constructTree(String prefix) {
return new Parser(prefix).parse();
}