Меню

Построить деревья для следующих арифметических выражений

Содержание урока

Вычисление арифметических выражений

Вычисление арифметических выражений

Один из способов вычисления арифметических выражений основан на использовании дерева. Сначала выражение, записанное в линейном виде (в одну строку), нужно «разобрать» и построить соответствующее ему дерево. Затем в результате прохода по этому дереву от листьев к корню вычисляется результат.

Нужно сначала найти последнюю операцию, просматривая выражение слева направо. Здесь последняя операция — это второе вычитание, оно оказывается в корне дерева (рис. 6.15).

Как выполнить этот поиск в программе? Известно, что операции выполняются в порядке приоритета (старшинства): сначала операции с более высоким приоритетом (слева направо), потом — с более низким (также слева направо). Отсюда следует важный вывод.

В корень дерева нужно поместить последнюю из операций с наименьшим приоритетом.

Теперь нужно построить таким же способом левое и правое поддеревья (рис. 6.16).

Левое поддерево требует ещё одного шага (рис. 6.17).

Эта процедура рекурсивная, её можно записать в виде псевдокода:

Рекурсия заканчивается, когда в оставшейся части строки нет ни одной операции, значит, там находится число (это лист дерева).

Теперь вычислим выражение по дереву. Если в корне находится знак операции, её нужно применить к результатам вычисления поддеревьев:

Снова получился рекурсивный алгоритм.

Возможен особый случай (на нём заканчивается рекурсия), когда корень дерева содержит число (т. е. это лист). Это число и будет результатом вычисления выражения.

Следующая страница Использование связанных структур

Cкачать материалы урока

Источник

Урок 4
Структура информации (простые структуры). Деревья. Графы
§4. Структура информации

Содержание урока

Задачи

Задачи

1. Определите выражения, соответствующие каждому из деревьев, в «нормальном» виде со скобками (эту форму называют инфиксной — операция записывается между данными). Постройте для каждого из них постфиксную форму.

2. Постройте деревья, соответствующие следующим арифметическим выражениям. Запишите эти выражения в префиксной и постфиксной формах:

Читайте также:  Постройте схему на которой кругами обозначьте три множества

3. Вычислите выражения, записанные в постфиксной форме:

Запишите каждое из них в инфиксной и в префиксной формах и постройте соответствующее дерево. Единственно ли такое дерево? В этом дереве назовите корень, листья и промежуточные вершины.

4. Нарисуйте граф, в котором 5 вершин и три компоненты связности. Постройте его матрицу смежности.

5. Структурируйте следующую информацию разными способами: «Между посёлками Верхний и Нижний есть просёлочная дорога длиной 10 км. Село Сергеево соединяется двумя асфальтовыми шоссе с Нижним (22 км) и Верхним (16 км). В село Солнечное можно доехать только из Сергеева по грунтовой дороге (5 км)». Можно ли сказать точно, как расположены эти пункты?

6. Для графа, полученного в предыдущей задаче, постройте матрицу смежности, список смежности, весовую матрицу. Является ли этот граф деревом?

7. Постройте матрицы смежности и весовые матрицы графов:

8. Постройте графы, соответствующие матрицам смежности.

9. Постройте графы, соответствующие весовым матрицам.

10. Стоимость перевозок между пунктами, которые для краткости обозначены буквами А, В, С, D и Е, задаётся таблицей (весовой матрицей графа). Нужно перевезти груз из пункта А в пункт В. Для каждого из четырёх вариантов определите оптимальный маршрут и полную стоимость перевозки.

11. Постройте орграфы, соответствующие весовым матрицам.

Для каждого из орграфов найдите количество различных маршрутов из вершины А во все остальные вершины.

Следующая страница Практическая работа № 1 «Оформление документа»

Cкачать материалы урока

Источник

Дерево выражений

Дерево выражений — это двоичное дерево, в котором каждый внутренний узел соответствует оператору, а каждый конечный узел соответствует операнду, поэтому, например, дерево выражений для 3 + ((5 + 9) * 2) будет иметь вид:

Обход по порядку в дереве выражений создает инфиксную версию заданного постфиксного выражения (то же самое, что и при обходе по предварительному заказу — префиксное выражение)

Оценка выражения, представленного деревом выражений:

Читайте также:  Сколько стоит построить баскетбольную площадку во дворе

Построение дерева выражений:
Теперь для построения дерева выражений мы используем стек. Мы перебираем входное выражение и делаем следующее для каждого символа.
1) Если символ является операндом, поместите его в стек
2) Если символ является оператором, извлеките два значения из стека, сделайте их дочерними и снова нажмите текущий узел.
В конце корнем дерева выражений будет только элемент стека.

Ниже приведена реализация:

// C ++ программа для дерева выражений
#include

using namespace std;

// Узел дерева выражений

// Утилита для проверки, если ‘c’
// оператор

bool isOperator( char c)

// Сервисная функция для выполнения обхода inorder

void inorder(et *t)

// Вспомогательная функция для создания нового узла

et* newNode( int v)

et *temp = new et;

temp->left = temp->right = NULL;

// Возвращает корень построенного дерева для данного
// постфиксное выражение

et* constructTree( char postfix[])

// Обход каждого символа

for ( int i=0; i strlen (postfix); i++)

// Если операнд, просто вставить в стек

// Вставляем два верхних узла

t1 = st.top(); // Магазин сверху

st.pop(); // Удалить верх

// сделать их детьми

// Добавить это подвыражение в стек

// корнем выражения будет только элемент

// Программа драйвера для тестирования выше

char postfix[] = «ab+ef*g*-» ;

et* r = constructTree(postfix);

printf ( «infix expression is \n» );

// Java-программа для построения дерева выражений

// Java-программа для дерева выражений

Node left, right;

left = right = null ;

// Утилита для проверки, если ‘c’

boolean isOperator( char c) <

// Сервисная функция для выполнения обхода inorder

void inorder(Node t) <

// Возвращает корень построенного дерева для данного

Node constructTree( char postfix[]) <

Stack st = new Stack();

// Обход каждого символа

for ( int i = 0 ; i

// Если операнд, просто вставить в стек

t = new Node(postfix[i]);

t = new Node(postfix[i]);

// Вставляем два верхних узла

t1 = st.pop(); // Удалить верх

// сделать их детьми

Читайте также:  Как построить сарай каменный

// System.out.println (t1 + «» + t2);

// Добавить это подвыражение в стек

// корнем выражения будет только элемент

public static void main(String args[]) <

ExpressionTree et = new ExpressionTree();

String postfix = «ab+ef*g*-» ;

char [] charArray = postfix.toCharArray();

Node root = et.constructTree(charArray);

System.out.println( «infix expression is» );

// Этот код предоставлен Mayank Jaiswal

# Python-программа для дерева выражений

# Узел дерева выражений

# Конструктор для создания узла

# Полезная функция для проверки, если ‘c’
# является оператором

if (c = = ‘+’ or c = = ‘-‘ or c = = ‘*’

# Полезная функция для обхода inorder

if t is not None :

# Возвращает корень построенного дерева для
# данное постфиксное выражение

# Обход каждого символа входного выражения

for char in postfix :

# если операнд, просто вставьте в стек

if not isOperator(char):

# Поп два верхних узла

# сделать их детьми

# Добавить это подвыражение в стек

# Только элемент будет корнем дерева выражений

# Программа драйвера для тестирования выше

print «Infix expression is»

// C # программа для построения дерева выражений

public class Node

public char value;

public Node left, right;

public Node( char item)

left = right = null ;

// Утилита для проверки, если ‘c’

Boolean isOperator( char c)

// Сервисная функция для выполнения обхода inorder

void inorder(Node t)

// Возвращает корень построенного дерева для данного

Node constructTree( char []postfix)

Stack st = new Stack();

// Обход каждого символа

for ( int i = 0; i

// Если операнд, просто вставить в стек

t = new Node(postfix[i]);

t = new Node(postfix[i]);

// Вставляем два верхних узла

t1 = (Node)st.Pop(); // Удалить верх

// сделать их детьми

// System.out.println (t1 + «» + t2);

// Добавить это подвыражение в стек

// только элемент будет корнем

public static void Main(String []args)

ExpressionTree et = new ExpressionTree();

String postfix = «ab+ef*g*-» ;

char [] charArray = postfix.ToCharArray();

Node root = et.constructTree(charArray);

Console.WriteLine( «infix expression is» );

// Этот код предоставлен Арнабом Кунду

Источник

Adblock
detector