Алгоритм построения дерева, представляющего префиксное выражение

Question

Я работаю над java программой, которая оценивает арифметическое выражение c prefix. Он принимает нормальное арифметическое c выражение, которое пользователь введет, затем преобразует его в префиксную форму. Например, если вы введете следующее выражение: 3 + (5 + 9) * 2 , оно преобразуется в: + 3 * + 592 . Затем он сохранит его в дереве выражений введите описание изображения здесь . Я ищу алгоритм для правильного хранения префиксного выражения в дереве. Я использую узел, который имеет значение 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

Когда я запускаю программу, она возвращает следующие ошибки:

Исключение в потоке "main" java .lang.StringIndexOutOfBoundsException: Строковый индекс вне диапазона: 8 в java .base /java.lang.StringLatin1.charAt(StringLatin1.java:47) в java .base / java .lang.String.charAt (String. java: 693) в Parser.parse (Parser . java: 12) в Parser.parse (Parser. java: 18) в Parser.parse (Parser. java: 18) в Main.constructTree (Main. java: 86) в Main.main (Main. java: 20)

Основное содержание функции:

    public static void main(String[] args)
    {
        System.out.println("Input the arithmetic expression");
        Scanner scan = new Scanner(System.in);
        String expInitiale = scan.nextLine();
        expInitiale = infixToPreFix(expInitiale).toString();
        System.out.println("Your expression in prefix form " + 
        expInitiale);

        /* Tree construction & evaluation of the expression (eval) */
         Noeud root = constructTree(expInitiale);
         double result = eval(root);
         System.out.println("The result is " + result);

    }

Answer 2

На самом деле, вы анализируете строку слева направо:

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());
    }
}

Базовый c алгоритм для чтения узла:

• чтение символа (следующий токен).
• , если этот символ является ди git, тогда верните новый листовой узел.
• в противном случае прочитайте еще два узла и создайте новый узел с такими, как левый и правый потомок .

Ваша функция constructTree будет такой:

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