Arhn - архитектура программирования

Создайте двоичное дерево из постфиксного выражения

Допустим, у меня есть следующее постфиксное выражение: 5372-*-

Я хочу создать двоичное дерево из этого выражения. Мой алгоритм таков: если мой символ - число, поместите его в стек, если это оператор, вытащите два элемента из стека и сделайте их дочерними элементами оператора. Затем поместите оператор в стек. Кажется, что это работает, но мне не удается соединить маленькие деревья, которые я создаю.

Мой текущий код:

public void myInsert(char ch, Stack s) {
    if (Character.isDigit(ch)) // initial cond.
        s.push(ch);
    else {
        TreeNode tParent = new TreeNode(ch);
        TreeNode t = new TreeNode(s.pop());
        TreeNode t2 = new TreeNode(s.pop());
        tParent.right = t;
        tParent.left = t2;
        s.push(ch);
        System.out.println("par" + tParent.ch);
        System.out.println("cright" + tParent.right.ch);
        System.out.println("cleft" + tParent.left.ch);
    }
}

Мой тестовый класс:

Stack stree = new Stack();

    BST b = new BST();
    String str = "5-3*(7-2)";
    String postfix = b.convertToPosFix(str);
    System.out.println(postfix);

    for (char ch : postfix.toCharArray()) {
         b.myInsert(ch, stree);

    }

Мой вывод:

par-
cright2
cleft7
par*
cright-
cleft3
par-
cright*
cleft5
java tree binary-tree infix-notation
21.03.2015

Ответы:


1

Используйте Stack из TreeNode, а не Stack символов. В конце концов, вы должны комбинировать TreeNode, а не char:

public void myInsert(char ch, Stack<TreeNode> s) {
    if (Character.isDigit(ch)) {
        // leaf (literal)
        s.push(new TreeNode(ch));
    } else {
        // operator node
        TreeNode tParent = new TreeNode(ch);

        // add operands
        tParent.right = s.pop();
        tParent.left = s.pop();

        // push result to operand stack
        s.push(tParent);
    }
}

узел дерева

public class TreeNode {
    public TreeNode right = null;
    public TreeNode left = null;
    public final char ch;

    TreeNode(char ch) {
        this.ch = ch;
    }

    @Override
    public String toString() {
        return (right == null && left == null) ? Character.toString(ch) : "(" + left.toString()+ ch + right.toString() + ")";
    }

}

основной

public static TreeNode postfixToTree(String s) {
    Stack<TreeNode> stree = new Stack<>();

    BST b = new BST();
    for (char ch : s.toCharArray()) {
        b.myInsert(ch, stree);
    }
    return stree.pop();
}

public static void main(String[] args) {
    System.out.println(postfixToTree("5372-*-"));
    System.out.println(postfixToTree("512+4*+3−"));
    System.out.println(postfixToTree("51*24*+"));
}

Это напечатает

(5-(3*(7-2)))
((5+((1+2)*4))−3)
((5*1)+(2*4))
21.03.2015
Новые материалы
Коллекции публикаций по глубокому обучению
Последние пару месяцев я создавал коллекции последних академических публикаций по различным подполям глубокого обучения в моем блоге https://amundtveit.com - эта публикация дает обзор 25..
Представляем: Pepita
Фреймворк JavaScript с открытым исходным кодом Я знаю, что недостатка в фреймворках JavaScript нет. Но я просто не мог остановиться. Я хотел написать что-то сам, со своими собственными..
Советы по коду Laravel #2
1-) Найти // You can specify the columns you need // in when you use the find method on a model User::find(‘id’, [‘email’,’name’]); // You can increment or decrement // a field in..
Работа с временными рядами спутниковых изображений, часть 3 (аналитика данных)
Анализ временных рядов спутниковых изображений для данных наблюдений за большой Землей (arXiv) Автор: Рольф Симоэс , Жильберто Камара , Жильберто Кейрос , Фелипе Соуза , Педро Р. Андраде ,..
3 способа решить квадратное уравнение (3-й мой любимый) -
1. Методом факторизации — 2. Используя квадратичную формулу — 3. Заполнив квадрат — Давайте поймем это, решив это простое уравнение: Мы пытаемся сделать LHS,..
Создание VR-миров с A-Frame
Виртуальная реальность (и дополненная реальность) стали главными модными терминами в образовательных технологиях. С недорогими VR-гарнитурами, такими как Google Cardboard , и использованием..
Демистификация рекурсии
КОДЕКС Демистификация рекурсии Упрощенная концепция ошеломляющей О чем весь этот шум? Рекурсия, кажется, единственная тема, от которой у каждого начинающего студента-информатика..