java算法来构建表示前缀表达式的树

Question

我正在开发一个计算算术前缀表达式的java程序。它接受用户将输入的普通算术表达式，然后将其转换为前缀形式。 例如，如果输入以下表达式：3+（5+9）*2，则会将其转换为： +3*+592。然后将其存储在表达式树enter image description here中。 我正在搜索一种算法，以便在树中正确存储前缀表达式我使用一个具有char值的节点和两个节点作为类属性 我已经做了所有的工作来计算表达式（使用树），我只需要将前缀表达式存储在树中。 如果您对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();
}